Course Schedule III

Problem

Each course has a duration and deadline. Find the maximum number of courses that can be taken.

Key insight (Greedy): Sort by deadline. For each course, add it. If total time > deadline, remove the longest course taken so far (to make room). Max-heap tracks course durations.

Solutions

// C++
int scheduleCourse(vector<vector<int>>& courses) {
    sort(courses.begin(), courses.end(), [](auto& a, auto& b){ return a[1] < b[1]; });
    priority_queue<int> maxH;
    int time = 0;
    for (auto& c : courses) {
        time += c[0];
        maxH.push(c[0]);
        if (time > c[1]) { time -= maxH.top(); maxH.pop(); }
    }
    return maxH.size();
}

// Java
public int scheduleCourse(int[][] courses) {
    Arrays.sort(courses, (a, b) -> a[1] - b[1]);
    PriorityQueue<Integer> maxH = new PriorityQueue<>(Collections.reverseOrder());
    int time = 0;
    for (int[] c : courses) {
        time += c[0];
        maxH.offer(c[0]);
        if (time > c[1]) { time -= maxH.poll(); }
    }
    return maxH.size();
}

// JavaScript
function scheduleCourse(courses) {
    courses.sort((a, b) => a[1] - b[1]);
    // Using sorted array as max-heap substitute
    const heap = [];
    let time = 0;
    for (const [dur, dead] of courses) {
        time += dur;
        // insert into sorted heap (descending)
        let pos = heap.findIndex(x => x < dur);
        if (pos === -1) heap.push(dur);
        else heap.splice(pos, 0, dur);
        if (time > dead) { time -= heap.shift(); } // remove largest
    }
    return heap.length;
}

# Python
import heapq

def scheduleCourse(courses):
    courses.sort(key=lambda c: c[1])  # sort by deadline
    max_heap = []  # negate for max-heap
    time = 0
    for dur, dead in courses:
        time += dur
        heapq.heappush(max_heap, -dur)
        if time > dead:
            # Remove the longest course
            time += heapq.heappop(max_heap)  # adds back negative = subtracts
    return len(max_heap)

Complexity

Time: O(n log n)
Space: O(n)

Key Insight

When we can't fit the current course (time > deadline), swap it with the longest course taken so far — this minimizes time used while maximizing course count. Always worthwhile if the longest is longer than current.