LC 0435 [M] Non overlapping Intervals - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=nONCGxWoUfM

time: O(nlogn)

A classic greedy case: interval scheduling problem.

The heuristic is: always pick the interval with the earliest end time. Then you can get the maximal number of non-overlapping intervals. (or minimal number to remove).
This is because, the interval with the earliest end time produces the maximal capacity to hold rest intervals.

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        
        res = 0
        prevEnd = intervals[0][1]
        for start, end in intervals[1:]:
            if start >= prevEnd:
                prevEnd = end # update earliest end time
            else:
                res += 1
                prevEnd = min(end, prevEnd) # pick the one that ends first (greedy)
        return res