Skip to main content
Talentd

Course Schedule III - Solution & Explanation

HardArrayGreedySortingHeap (Priority Queue)11 min readAsked at: Amazon, Meta, Salesforce +1
Practice this problem

Problem Statement

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 <= 104
  • 1 <= 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.

  1. Sort the courses based on their last day to prioritize courses that need to be completed earlier.
  2. Iteratively add each course to a max-heap which allows keeping track of the courses currently selected based on their durations.
  3. 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.
  4. The size of the max-heap at the end represents the maximum number of courses that can be fit into the schedule.

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

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.

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.

Code

Java

Java

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach Using Max-Heap

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.

Dynamic Programming Approach

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.

Greedy + Priority Queue (Max-Heap)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Max-HeapO(n log n)O(n)Best general solution. Efficient for large inputs and commonly expected in interviews.
Dynamic ProgrammingO(n * D)O(n * D)Useful for understanding the decision process or when deadlines are small enough to make DP feasible.

Video Solution

Course Schedule III | Live Coding with Explanation | Leetcode - 630 • Algorithms Made Easy • 13,696 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Course Schedule III with our built-in code editor and test cases.

Practice on FleetCode
Previous

Course Schedule

Next

Course Schedule II