Course Schedule III solution and explanation
9 more videos on this problem
Course Schedule III | Live Coding with Explanation | Leetcode - 630Algorithms Made Easy · 13:38 · 13K views
Course Schedule III | Leetcode 630 | Leetcode Hard | LC 630 | LC Hard | Live Coding sessionCoding Decoded · 13:30 · 2K views
Leetcode [630] Course Schedule IIISDE Skills · 29:06 · 2K views
Leetcode - Course Schedule III (Python)Timothy H Chang · 5:27 · 2K views
LeetCode 630. Course Schedule IIIHappy Coding · 21:28 · 2K views
Course Schedule III | Heap | Multiset | 630 LeetCode | LeetCode Explore | Day 02CodeWithSunny · 18:48 · 2K views
Leetcode 630 Course Schedule III | 3 Approaches | Checkout Coding Decoded SDE SheetCoding Decoded · 2:11 · 1K views
630. Course Schedule IIITech Adora by Nivedita · 14:13 · 1K views
Course Schedule III | LeetCode 630 | Coders CampCoders Camp · 16:30 · 895 views
Daily Leetcode #814: Jun 23, 2022 - 630. Course Schedule IIIProgramming Live with Larry · 15:56 · 872 views
The problem
There are n different online courses numbered from 1 to n. You are given an array courses where courses[i] = [durationi, lastDayi] indicate that the ith course should be taken continuously for durationi days and must be finished before or on lastDayi.
You will start on the 1st day and you cannot take two or more courses simultaneously.
Return the maximum number of courses that you can take.
Example 1:
Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]] Output: 3 Explanation: There are totally 4 courses, but you can take 3 courses at most: First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day. Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day. Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day. The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.
Example 2:
Input: courses = [[1,2]] Output: 1
Example 3:
Input: courses = [[3,2],[4,3]] Output: 0
Constraints:
1 <= courses.length <= 1041 <= durationi, lastDayi <= 104
Approach overview
Problem Overview: You are given courses where each course has a duration and a deadline. The goal is to take the maximum number of courses such that the total time spent never exceeds the deadline of any course you take.
Approach 1: Greedy with Max-Heap (Priority Queue) (Time: O(n log n), Space: O(n))
The key insight is that earlier deadlines should be handled first. Start by sorting all courses by their deadline using sorting. Then iterate through the courses and keep track of the total time spent. Each time you take a course, add its duration to the running total and push that duration into a max-heap from the heap (priority queue) category.
If the total time exceeds the current course's deadline, remove the course with the longest duration from the heap. This works because replacing a long course with a shorter one frees up time while keeping the course count high. The heap always stores durations of the courses you have chosen so far, and removing the maximum duration ensures the schedule remains feasible.
This greedy strategy works because deadlines enforce a natural order, and removing the longest course provides the best chance of fitting more courses later. The heap operations (push and pop) take O(log n), so the overall complexity becomes O(n log n) after sorting. This is the most efficient and widely accepted solution using concepts from greedy algorithms and array processing.
Approach 2: Dynamic Programming (Time: O(n * D), Space: O(n * D))
Dynamic programming models the problem as selecting courses while tracking the total time spent. First sort courses by deadline. Define a DP state where dp[i][t] represents whether it is possible to finish some subset of the first i courses using exactly t time. For each course, you either skip it or include it if the resulting total time does not exceed its deadline.
Transitions update the DP table by checking whether adding the current course duration keeps the schedule valid. The maximum number of courses can then be derived from the valid states. While this approach clearly expresses the decision process, it becomes expensive when deadlines are large because the DP dimension grows with total time.
Recommended for interviews: Interviewers expect the greedy + max-heap solution. Sorting by deadline shows you understand the scheduling constraint, and using a heap to drop the longest course demonstrates strong algorithmic intuition. The dynamic programming formulation shows correctness reasoning but is rarely optimal for production or interview settings due to higher time and space costs.
Approach 1: Greedy Approach Using Max-Heap
This approach involves using a greedy method combined with a max-heap (or priority queue) to choose which courses to take.
- Sort the courses based on their last day to prioritize courses that need to be completed earlier.
- Iteratively add each course to a max-heap which allows keeping track of the courses currently selected based on their durations.
- If adding a new course exceeds the current day deadline in the schedule, remove the course with the longest duration from the heap. This is done because replacing the longest course is less detrimental to the schedule than other courses.
- The size of the max-heap at the end represents the maximum number of courses that can be fit into the schedule.
import heapq
def scheduleCourse(courses):
courses.sort(key=lambda x: x[1])
max_heap = []
total_days = 0
for duration, last_day in courses:
if total_days + duration <= last_day:
total_days += duration
heapq.heappush(max_heap, -duration)
elif max_heap and -max_heap[0] > duration:
total_days += duration + heapq.heappop(max_heap)
heapq.heappush(max_heap, -duration)
return len(max_heap)#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int scheduleCourse(vector<vector<int>>& courses) {
sort(courses.begin(), courses.end(), [](const vector<int> &a, const vector<int> &b) {
return a[1] < b[1];
});
priority_queue<int> max_heap;
int total_days = 0;
for (const auto& course : courses) {
int duration = course[0], last_day = course[1];
if (total_days + duration <= last_day) {
total_days += duration;
max_heap.push(duration);
} else if (!max_heap.empty() && max_heap.top() > duration) {
total_days += duration - max_heap.top();
max_heap.pop();
max_heap.push(duration);
}
}
return max_heap.size();
}This Python solution sorts the courses based on their last available day. It utilizes a max-heap (by pushing negative durations) to manage the courses being taken such that the longest duration course is easily removable when a constraint breach occurs. The heap size at the end represents the number of courses taken.
Time Complexity: O(n log n), where n is the number of courses, due to sorting and heap operations.
Space Complexity: O(n), required for the heap storage.
Approach 2: Dynamic Programming Approach
This approach defines a DP table where `dp[i][t]` represents the maximum number of courses we can fit into our schedule given the first `i` courses considered and `t` days available. The decision at each step involves either taking or not taking a course. The transition function will decide by taking the maximum between taking the current course (if it fits) or not taking it.
import java.util.*;
public class CourseSchedule {
public int scheduleCourse(int[][] courses) {
Arrays.sort(courses, Comparator.comparingInt(a -> a[1]));
int n = courses.length;
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
for (int t = courses[i - 1][1]; t >= courses[i - 1][0]; t--) {
dp[t] = Math.max(dp[t], dp[t - courses[i - 1][0]] + 1);
}
}
return Arrays.stream(dp).max().getAsInt();
}
}This Java solution uses a dynamic programming approach to solve the problem efficiently by iterating backwards through possible days to ensure overlapping updates do not occur, thus propagating maximum course counts correctly at each considered day.
Time Complexity: O(nD), where n is the number of courses and D is the maximum last day.
Space Complexity: O(D) for the DP array.
Approach 3: Greedy + Priority Queue (Max-Heap)
We can sort the courses in ascending order by their end time, and each time select the course with the earliest deadline to take.
If the total time s of the selected courses exceeds the end time last of the current course, we remove the course with the longest duration from the previously selected courses, until the constraint of the current course's end time is satisfied. Here we use a priority queue (max-heap) pq to maintain the durations of the currently selected courses, and each time we pop the course with the longest duration from the priority queue to remove it.
Finally, the number of elements in the priority queue is the maximum number of courses we can take.
The time complexity is O(n times log n) and the space complexity is O(n), where n is the number of courses.
function scheduleCourse(courses: number[][]): number {
courses.sort((a, b) => a[1] - b[1]);
const pq = new MaxPriorityQueue<number>();
let s = 0;
for (const [duration, last] of courses) {
pq.enqueue(duration);
s += duration;
while (s > last) {
s -= pq.dequeue();
}
}
return pq.size();
}func scheduleCourse(courses [][]int) int {
sort.Slice(courses, func(i, j int) bool { return courses[i][1] < courses[j][1] })
pq := &hp{}
s := 0
for _, e := range courses {
duration, last := e[0], e[1]
s += duration
pq.push(duration)
for s > last {
s -= pq.pop()
}
}
return pq.Len()
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
func (h *hp) push(v int) { heap.Push(h, v) }
func (h *hp) pop() int { return heap.Pop(h).(int) }Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach Using Max-Heap | Time Complexity: O(n log n), where n is the number of courses, due to sorting and heap operations. |
| Dynamic Programming Approach | Time Complexity: O(nD), where n is the number of courses and D is the maximum last day. |
| Greedy + Priority Queue (Max-Heap) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Max-Heap | O(n log n) | O(n) | Best general solution. Efficient for large inputs and commonly expected in interviews. |
| Dynamic Programming | O(n * D) | O(n * D) | Useful for understanding the decision process or when deadlines are small enough to make DP feasible. |
Frequently asked questions
Is Course Schedule III easy or hard?
Course Schedule III is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the greedy insight: when the schedule exceeds a deadline, removing the longest course preserves flexibility for future courses.
Course Schedule III Python/Java solution
Python and C++ implementations typically use a max-heap with greedy scheduling. Java solutions sometimes demonstrate both the priority queue approach and a dynamic programming formulation. The heap-based version runs in O(n log n) and is the standard interview solution.
How to solve Course Schedule III in O(n)?
A true O(n) solution is not generally achievable because sorting by deadline is required to process courses in the correct order. The best practical complexity is O(n log n) using sorting and a max-heap. This ensures efficient course replacement when deadlines are violated.
What is the best approach for Course Schedule III?
The optimal solution uses a greedy strategy combined with a max-heap (priority queue). Sort courses by deadline, add each course duration to a running total, and store durations in a max-heap. If the total time exceeds the deadline, remove the longest course from the heap. This keeps the schedule valid while maximizing the number of courses.
Is Course Schedule III asked at Google/Amazon/Meta?
Course Schedule III is a common hard-level interview problem at companies like Google, Amazon, and Meta. It tests understanding of greedy scheduling, priority queues, and optimization under constraints. Candidates are often expected to derive the heap-based greedy solution.
What data structure is used in Course Schedule III?
The core data structure is a max-heap (priority queue). It stores durations of the courses currently selected, allowing the algorithm to quickly remove the longest course when the total schedule time exceeds a deadline.
What is the time complexity of Course Schedule III?
The optimal greedy solution runs in O(n log n) time. Sorting the courses by deadline takes O(n log n), and each heap insertion or removal costs O(log n). Space complexity is O(n) because the heap stores durations of the selected courses.