Course Schedule III — Solution in Python, Java & C++
Course Schedule III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and sorting.
Course Schedule III is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Greedy, Heap
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n online courses. Course i is courses[i] = [duration, lastDay]: it takes duration consecutive days and must be finished on or before day lastDay.
You start on day 1 and can study only one course at a time; a course taken from day s occupies days s through s + duration - 1. Courses you skip cost nothing.
Return the maximum number of courses you can complete.
Example 1
Input: courses = [[3,5],[2,4],[4,9],[5,9]]
Output: 3
Explanation: Take the 2-day course (done day 2), the 3-day one (done day 5) and the 4-day one (done day 9). All four would need 14 days.
Example 2
Input: courses = [[1,2]]
Output: 1
Example 3
Input: courses = [[3,2],[4,3]]
Output: 0
Explanation: Neither course fits before its own deadline.
Constraints
1 <= courses.length <= 10^41 <= duration, lastDay <= 10^4
Hints for Course Schedule III
Hint 1
Any set of courses that can be completed can be completed in order of their deadlines.
Hint 2
Walk the courses by deadline and tentatively take each one, tracking the total time used.
Hint 3
If the total overshoots the current deadline, drop the longest course taken so far (a max-heap) — that frees the most time for the same count.
How to solve Course Schedule III
Two facts make a greedy work: a feasible set stays feasible when sorted by deadline, and when a new course pushes the total time past its deadline, removing the longest course taken so far keeps the count while leaving the most slack for the future.
Approach
- Sort the courses by
lastDay. - Keep
time(days used) and a max-heap of the durations taken. - For each course: add its duration to
timeand push it. Iftime > lastDay, pop the largest duration and subtract it. - Return the heap size.
Why it works
By an exchange argument, among all ways to complete k courses from the first i (in deadline order), the greedy keeps one with the smallest total time — after each step the heap holds the best set of its size. Adding a course either fits (count grows) or does not, in which case dropping the longest duration (possibly the new one) keeps the count and minimises time. Because later deadlines are larger, a smaller total time is never worse for anything that follows.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Sorting by duration instead of deadline fails: a short course with a far deadline should wait.
- When the overshoot happens, the course to drop may be the one just added — push first, then pop the maximum.
- A course whose
durationexceeds its ownlastDaycan never be kept; the push-then-pop handles it without a special case.
Reference solution
Python
from typing import List
import heapq
def scheduleCourse(courses: List[List[int]]) -> int:
heap = [] # negated durations of the courses kept
time = 0
for duration, last in sorted(courses, key=lambda c: c[1]):
time += duration
heapq.heappush(heap, -duration)
if time > last:
time += heapq.heappop(heap) # drop the longest course so far
return len(heap)Java
public static int scheduleCourse(int[][] courses) {
int[][] cs = courses.clone();
Arrays.sort(cs, (a, b) -> Integer.compare(a[1], b[1]));
PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
int time = 0;
for (int[] c : cs) {
time += c[0];
heap.add(c[0]);
if (time > c[1]) time -= heap.poll(); // drop the longest course so far
}
return heap.size();
}C++
int scheduleCourse(vector<vector<int>>& courses) {
vector<vector<int>> cs = courses;
sort(cs.begin(), cs.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
priority_queue<int> heap;
int time = 0;
for (auto& c : cs) {
time += c[0];
heap.push(c[0]);
if (time > c[1]) {
time -= heap.top(); // drop the longest course so far
heap.pop();
}
}
return heap.size();
}JavaScript
var scheduleCourse = function(courses) {
var cs = courses.slice().sort(function(a, b) { return a[1] - b[1]; });
var heap = []; // negated durations of the courses kept
var time = 0;
for (var i = 0; i < cs.length; i++) {
time += cs[i][0];
heapPush(heap, -cs[i][0]);
if (time > cs[i][1]) time += heapPop(heap); // drop the longest course so far
}
return heap.length;
};
var heapPush = function(h, v) {
h.push(v);
var i = h.length - 1;
while (i > 0) {
var p = (i - 1) >> 1;
if (h[p] <= h[i]) break;
var t = h[p]; h[p] = h[i]; h[i] = t;
i = p;
}
};
var heapPop = function(h) {
var top = h[0];
var last = h.pop();
if (h.length > 0) {
h[0] = last;
var j = 0;
for (;;) {
var l = 2 * j + 1, r = l + 1, s = j;
if (l < h.length && h[l] < h[s]) s = l;
if (r < h.length && h[r] < h[s]) s = r;
if (s === j) break;
var t = h[s]; h[s] = h[j]; h[j] = t;
j = s;
}
}
return top;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms