274. Course Schedule III

Process courses in deadline order and greedily take each one. If the running total time exceeds the current deadline, drop the single longest course taken so far (from a max-heap of durations) — swapping it out never reduces the count and can only free up time.

Greedy by deadline, with a regret step

Sort courses by lastDay ascending, then consider them in that order while tracking time = total days scheduled so far and a max-heap of the durations of chosen courses.

For each course (dur, end):

1. Tentatively take it: time += dur, push dur onto the heap.
2. If time > end (deadline blown), pop the longest duration from the heap and subtract it from time.

Step 2 is the key insight: if we've overshot, removing the longest course we've committed to is always at least as good — it frees the most time while keeping the count non-decreasing. The answer is the heap's size at the end.

courses.sort(by lastDay)
heap = []; time = 0
for dur, end in courses:
    time += dur; push -dur onto max-heap
    if time > end: time += pop_max()   # remove longest
return len(heap)

Worked example

courses = [[100,200],[200,1300],[1000,1250],[2000,3200]] → sorted by deadline: [100,200],[1000,1250],[200,1300],[2000,3200].

• [100,200]: time 100 (<=200). heap {100}.
• [1000,1250]: time 1100 (<=1250). heap {1000,100}.
• [200,1300]: time 1300 (<=1300). heap {1000,200,100}.
• [2000,3200]: time 3300 > 3200 → drop longest (2000) → time 1300. heap size 3.

Answer 3.

Complexity

• Time: O(n log n).
• Space: O(n) for the heap.

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        int time = 0;
        for (int[] c : courses) {
            int dur = c[0], end = c[1];
            time += dur;
            heap.offer(dur);
            if (time > end) {
                time -= heap.poll();  // remove the longest course
            }
        }
        return heap.size();
    }
}