leetcode-greedy

435. Non-overlapping Intervals.py

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        """
        Greedy problem because of pattern: "Find minimum or maximum number of something to do something"
        
        T: O(nlogn)
        S: O(1). No extra space is used.
        
        Reference: https://leetcode.com/problems/non-overlapping-intervals/discuss/276056/Python-Greedy-Interval-Scheduling
        """
        ending_time, ans = float('-inf'), 0 # the earliest end time
        for i in sorted(intervals, key=lambda x: x[1]):
            start_time = i[0]
            if start_time >= ending_time: 
                # always pick up the current earliest ending time
                ending_time = i[1]
            else: 
                ans += 1
        return ans