LC630. Course Schedule III

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        """ tc O(NlgN) sc O(N)
        main idea: greedy 
        1. sort by ddl then push duration into heap (note, in negtive value)
        2. start from t=0, if t +current_duration <= ddl, push into hp 
        3. if hp[0] > current_duration, pop out bigger duration, update t    
        4. class to ake is size of queue
        """
        courses.sort(key=lambda x: x[1])
        q = []
        t = 0
        for c in courses:
            if t + c[0] <= c[1]:
                # add duration time into q 
                heapq.heappush(q,-c[0])
                t += c[0]
            # If it exceeds deadline, I can swap current course with current courses that has biggest duration.
            elif q and -q[0] > c[0]:
                t += c[0] + heapq.heappop(q)
                heapq.heappush(q,-c[0])
        return len(q)