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 <= 104Problem 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.
This approach involves using a greedy method combined with a max-heap (or priority queue) to choose which courses to take.
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.
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.
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.
Java
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.
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.
Python
Java
C++
Go
TypeScript
| 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) | — |
| 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. |
Course Schedule III | Live Coding with Explanation | Leetcode - 630 • Algorithms Made Easy • 13,163 views views
Watch 9 more video solutions →Practice Course Schedule III with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor