Course Schedule III

Share

Given courses where courses[i] = [duration_i, lastDay_i], find the maximum number of courses you can take. Each course must finish by its lastDay.

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

Solution Approach

Sort by deadline. Greedily take each course; if total time exceeds deadline, replace the longest previously taken course if it is longer than current course.

  • Sort by lastDay.
  • Max-heap tracks durations of taken courses.
  • For each course: add duration to time and heap.
  • If time > lastDay: pop max duration from heap, subtract from time.
  • Answer = heap.size().
Java
import java.util.*;

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a,b) -> a[1] - b[1]);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int time = 0;
        for (int[] c : courses) {
            time += c[0]; maxHeap.offer(c[0]);
            if (time > c[1]) time -= maxHeap.poll();
        }
        return maxHeap.size();
    }
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(N)