Non Overlapping Intervals

---

Intuition

• Notice that if we sort by end time, the only time in which an overlap occurs is when the start time of the interval with greater end time is less than the end time of the previous interval.
• Keep track of the end time of the non overlapped interval (thereby simulating a removal). Then, for the next interval, check if its start time occurs before that end time.

Complexity

Runtime

Space

Code

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
 
        tracked_end_time = intervals[0][1]  # keep the first interval
        res = 0
 
        for i in range(1, len(intervals)):
            if tracked_end_time > intervals[i][0]:
                # overlap — remove this interval
                res += 1
            else:
                # no overlap — keep this interval
                tracked_end_time = intervals[i][1]
 
        return res

Notes

Drive

Cards

START Basic Front: Non Overlapping Intervals Back: Compare end time to start time of next. END

---

References

• Non Overlapping Intervals