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.
Example 1:
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.
Example 2:
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.
Example 3:
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.
Constraints:
1 <= intervals.length <= 10^5
intervals[i].length == 2
-5 * 10^4 <= start_i < end_i <= 5 * 10^4
This problem asks us to find the minimum number of intervals to remove from a given set of intervals such that the remaining intervals are non-overlapping.
A brute-force approach would involve generating all possible subsets of the intervals and, for each subset, checking if the intervals are non-overlapping. We keep track of the maximum size of non-overlapping subsets. The number of intervals to remove would be the original number of intervals minus the maximum size of a non-overlapping subset. This approach is highly inefficient.
A more efficient approach uses a greedy algorithm. The key idea is to sort the intervals based on their end times. Then, we iterate through the sorted intervals and keep track of the last non-overlapping interval. If the current interval overlaps with the last non-overlapping interval, we increment the count of intervals to remove. Otherwise, we update the last non-overlapping interval to the current interval.
Algorithm:
remove_count
to 0.last_end
to negative infinity (or the smallest possible value).last_end
, then it overlaps with the previous non-overlapping interval. Increment remove_count
.last_end
to the end time of the current interval.remove_count
.Example:
Let's consider the intervals [[1,2],[2,3],[3,4],[1,3]]
.
[[1,2],[2,3],[3,4],[1,3]]
becomes [[1,2],[2,3],[1,3],[3,4]]
remove_count = 0
last_end = -infinity
Iteration:
[1,2]
: 1 >= last_end
. last_end = 2
[2,3]
: 2 >= last_end
. last_end = 3
[1,3]
: 1 < last_end
. remove_count = 1
[3,4]
: 3 >= last_end
. last_end = 4
Return remove_count = 1
Code (Python):
def eraseOverlapIntervals(intervals):
intervals.sort(key=lambda x: x[1]) # Sort by end times
remove_count = 0
last_end = float('-inf')
for start, end in intervals:
if start < last_end:
remove_count += 1
else:
last_end = end
return remove_count
sort
function is implemented using Timsort, which has an average space complexity of O(n).