Course Schedule III

Problem Id: 630 Difficulty: Hard


Intuition

Solution


class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda x: [x[1], x[0]])
        heap = []
        s = 0
        count = 0
        for t, d in courses:
            if s + t <= d:
                heapq.heappush(heap, -t)
                s += t
                count += 1
            elif not heap:
                pass
            else:
                top = -heap[0]
                if top >= t:
                    heapq.heappop(heap)
                    s -= top
                    s += t
                    heapq.heappush(heap, -t)
        return count