LeetCode Meditations: Non-overlapping Intervals

The description for Non-overlapping Intervals is:

Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

For example:

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1

Explanation: [1, 3] can be removed and the rest of the intervals are non-overlapping.

Or:

Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2

Explanation: You need to remove two [1, 2] to make the rest of the intervals non-overlapping.

Or:

Input: intervals = [[1, 2], [2, 3]]
Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

---

For this problem, NeetCode has a great solution that starts with sorting the intervals, as we did in the previous problem.
We can also initialize a variable to keep track of the number of removals.

intervals.sort((a, b) => a[0] - b[0]);

let numRemovals = 0;

Now that our intervals are sorted, we'll go through each one, checking whether they overlap or not. We'll keep track of the previous interval's end for that, so let's initialize a prevEnd variable that initially holds the first interval's end:

let prevEnd = intervals[0][1];

Note

For two intervals

Note

For two intervals not to overlap, the start of one should be strictly larger than the end of the other or the end of the one should be strictly smaller than the start of the other, as mentioned in our chapter introduction.

not to overlap, the start of one should be strictly larger than the end of the other or the end of the one should be strictly smaller than the start of the other, as mentioned in our chapter introduction.

In this problem, when the end of an interval is equal to the other's start, they are considered non-overlapping.

So, here we can say that two intervals will overlap if the start of one is strictly less than the end of the other. In that case, we'll update prevEnd to be the lesser value of the two ends so that we have a less chance of overlapping with the next interval. Otherwise, we'll continue as before:

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1

Explanation: [1, 3] can be removed and the rest of the intervals are non-overlapping.

Finally, we can return numRemovals:

Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2

Explanation: You need to remove two [1, 2] to make the rest of the intervals non-overlapping.

And, the final solution we have looks like this:

Input: intervals = [[1, 2], [2, 3]]
Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Time and space complexity

Since we sort the intervals at the start, the time complexity will be $O(nlogn)$O(n log n) . We don't have an additional data structure whose size will increase as the input size increases, so the space complexity is $O(1)$O(1) .

---

Next up, we will start the last chapter of the series, Bit Manipulation. Until then, happy coding.

The above is the detailed content of LeetCode Meditations: Non-overlapping Intervals. For more information, please follow other related articles on the PHP Chinese website!