Course Schedule III

Intuition

Sorting by deadline lets us consider courses in the order their windows close, which is the order in which commitments become urgent. We optimistically take every course and accumulate the elapsed time so far. Whenever the running time passes the current course's deadline, at least one previously chosen course must be dropped, and dropping the one with the largest duration frees the most time while removing only a single course. A max-heap keeps the largest taken duration at hand for instant eviction, and because each eviction removes exactly one course, the final heap size is the maximum number of courses that fit.

Algorithm walkthrough

1. 1Sort the courses in non-decreasing order of their last allowed day.
2. 2Iterate through the sorted courses, adding each duration to a running total of consumed days and pushing that duration onto a max-heap.
3. 3If the running total now exceeds the current course's deadline, pop the largest duration from the heap and subtract it from the total.
4. 4This keeps the selected set feasible while never reducing its size below the best achievable so far.
5. 5After processing every course, the number of elements remaining in the heap is the answer.

Implementation

import heapq
from typing import List

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda x: x[1])
        heap = []  # max-heap via negated durations
        time = 0
        for duration, last_day in courses:
            time += duration
            heapq.heappush(heap, -duration)
            if time > last_day:
                time += heapq.heappop(heap)  # popped value is negative
        return len(heap)