Comment on page
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.
- 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.
[ [1,2], [2,3], [3,4], [1,3] ]
[1,3] can be removed and the rest of intervals are non-overlapping.
[ [1,2], [1,2], [1,2] ]
You need to remove two [1,2] to make the rest of intervals non-overlapping.
[ [1,2], [2,3] ]
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]
if len(intervals) == 0:
intervals.sort(key=lambda interval: interval.end)
removal_count = 0
prev_start = intervals.end
for i in range(1, len(intervals)):
if intervals[i].start < prev_start:
removal_count += 1
prev_start = intervals[i].end