Non-Overlapping Intervals
- 1 min read
- Interval
- LC-Medium
3 years ago
Solution
- Sort your intervals.
- Bro this question is so simple just use your intuition
- When you have two overlapping intervals, you need to remove one. But which one do you remove?
- You remove the interval with the later ending time, because you want to lower your chances of your new interval overlapping with the next interval
- Similar to Merge Intervals, we look at two intervals at a time, but here instead, we only care about the end time.
- That is, when two intervals are overlapping, for your next iteration, the interval you will use to compare is the one with the earlier end time.
- This means, the interval with the later end time will be removed. This is when you'd increment your counter variable.
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[0])
prev_interval_end = intervals[0][1]
to_remove = 0
for i in range(1, len(intervals)):
if intervals[i][0] < prev_interval_end:
to_remove += 1
prev_interval_end = min(prev_interval_end, intervals[i][1])
else:
prev_interval_end = intervals[i][1]
return to_remove