Course Schedule III

Share

Given courses with duration and deadline, find max number of courses you can take.

Example 1
Input: courses=[[100,200],[200,1300],[1000,1250],[2000,3200]] → Output: 3
Example 2
Input: courses=[[1,2]] → Output: 1

Solution Approach

Sort by deadline. Use a max-heap: greedily take each course; if taking it exceeds deadline, replace longest course taken so far.

  • Sort courses by deadline (last day)
  • Use max-heap of durations
  • For each course: add it and update current time
  • If current time > deadline: remove longest course from heap
  • Return heap size
Java
public int scheduleCourse(int[][] courses) {
    Arrays.sort(courses, (a, b) -> a[1] - b[1]);
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    int time = 0;
    for (int[] c : courses) {
        pq.offer(c[0]);
        time += c[0];
        if (time > c[1]) {
            time -= pq.poll();
        }
    }
    return pq.size();
}
  • Time Complexity: O(n log n)
  • Space Complexity: O(n)