435 Non-overlapping Intervals
Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note:
- 1.You may assume the interval's end point is always bigger than its start point.
- 2.Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.
Example 1:
Input:
[ [1,2], [2,3], [3,4], [1,3] ]
Output:
1
Explanation:
[1,3] can be removed and the rest of intervals are non-overlapping.
Example 2:
Input:
[ [1,2], [1,2], [1,2] ]
Output:
2
Explanation:
You need to remove two [1,2] to make the rest of intervals non-overlapping.
Example 3:
Input:
[ [1,2], [2,3] ]
Output:
0
Explanation:
You don't need to remove any of the intervals since they're already non-overlapping.
The Idea: This is uni-weight interval scheduling problem. Sort by finish, then increment every-time it overlaps with the previous valid interval.
Complexity: O(nlogn +n) time, O(1) space
def eraseOverlapIntervals(self, intervals):
"""
:type intervals: List[Interval]
:rtype: int
"""
if len(intervals) == 0:
return 0
intervals.sort(key=lambda interval: interval.end)
removal_count = 0
prev_start = intervals[0].end
for i in range(1, len(intervals)):
if intervals[i].start < prev_start:
removal_count += 1
else:
prev_start = intervals[i].end
return removal_count
Last modified 3yr ago