Course Schedule III
Problem
Each course has (duration, lastDay). Maximize the number you can finish.
courses=[[100,200],[200,1300],[1000,1250],[2000,3200]]3def schedule_courses(courses):
import heapq
courses.sort(key=lambda c: c[1])
h, t = [], 0
for d, end in courses:
heapq.heappush(h, -d); t += d
if t > end: t += heapq.heappop(h)
return len(h)function scheduleCourses(courses) {
courses.sort((a, b) => a[1] - b[1]);
const h = []; let t = 0;
const up = i => { while (i && h[(i-1)>>1] < h[i]) { [h[i], h[(i-1)>>1]] = [h[(i-1)>>1], h[i]]; i = (i-1)>>1; } };
const down = i => { while (true) { let l = i*2+1, r = i*2+2, m = i; if (l < h.length && h[l] > h[m]) m = l; if (r < h.length && h[r] > h[m]) m = r; if (m === i) break; [h[i], h[m]] = [h[m], h[i]]; i = m; } };
for (const [d, e] of courses) {
h.push(d); up(h.length - 1); t += d;
if (t > e) { t -= h[0]; h[0] = h[h.length-1]; h.pop(); down(0); }
}
return h.length;
}int scheduleCourse(int[][] courses) {
Arrays.sort(courses, (a, b) -> a[1] - b[1]);
PriorityQueue pq = new PriorityQueue<>(Comparator.reverseOrder());
int t = 0;
for (int[] c : courses) {
pq.offer(c[0]); t += c[0];
if (t > c[1]) t -= pq.poll();
}
return pq.size();
} int scheduleCourse(vector>& courses) {
sort(courses.begin(), courses.end(), [](auto& a, auto& b){ return a[1] < b[1]; });
priority_queue pq; int t = 0;
for (auto& c : courses) {
pq.push(c[0]); t += c[0];
if (t > c[1]) { t -= pq.top(); pq.pop(); }
}
return pq.size();
} Explanation
We want to finish as many courses as possible, where each has a duration and a lastDay deadline. The plan: consider courses in order of their deadline, greedily take each one, but keep the freedom to drop the longest course so far if our schedule overruns.
We sort by lastDay so deadlines arrive in increasing order, and we track total time t spent. We use a max-heap of durations (stored as negatives, since Python's heap is a min-heap) to remember the courses we have tentatively taken.
For each course we tentatively add its duration to t and push it onto the heap. If t now exceeds the current deadline end, we pop the longest course taken so far and subtract its time. Removing the biggest offender frees the most room while keeping the course count as high as possible.
Why this is safe: swapping out the longest course never reduces how many courses we keep, and it always leaves the most slack for future courses with tighter deadlines. At the end, the heap size is the maximum number of courses.
Example: [[100,200],[200,1300],[1000,1250],[2000,3200]]. Sorted by deadline we take 100, then 200, then 1000 (total 1300 > 1250, so drop the 1000), then 200; the final heap holds 3 courses.