Heap / Priority Queue - Course Schedule III

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.

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

Input: [[1,2]] → Output: 1

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().

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)