630. Course Schedule III
Problem Description
In this problem, you are given n
online courses, each with a specified duration and a deadline by which it should be completed. The courses must be taken one at a time, consecutively, from day 1 onwards. The goal is to find out the most number of courses you can finish before their respective deadlines.
Each course is described by two parameters: duration
(how many days it takes to complete the course) and lastDay
(the last day by which the course must be completed). You are provided this information in an array courses
, where each element courses[i]
is another array with two elements: [duration_i, lastDay_i]
.
Your task is to pick the courses in such a way that you can complete the maximum number of them within their deadlines, keeping in mind that you cannot take more than one course at a time.
Intuition
The solution to this problem involves sorting and priority queues, specifically a min-heap. The first step is to sort the courses by their deadline (lastDay
). This initial sort helps to align our course selections in the direction that we attempt to tackle courses with earlier deadlines first.
After sorting the courses by their deadlines, we iterate through each course. As we go through the courses, we add each course's duration to a total duration accumulator (s
) and push the negative of duration onto a min-heap (pq
). We use a min-heap to keep track of the courses with the longest duration that we have attended to, and the reason for storing negative durations is to effectively turn the min-heap into a max-heap (since Python's heapq
only provides a min-heap).
If at any point our total duration accumulator (s
) exceeds the current course's last day, it means we cannot finish the current course before the deadline. To rectify this, we start removing the longest courses we have taken from our schedule (the top of the heap), until s
no longer exceeds the last day of the current course.
By iteratively adding courses and potentially removing the longest course from our schedule whenever necessary, we ensure that we are always in a position to have completed the maximum number of courses by their respective deadlines.
The solution's efficiency comes from the fact that when we must drop a course, we drop the one with the longest duration, which has the most significant potential to free up our schedule for fitting in more courses.
The final answer is the number of courses we have in our priority queue, as this represents the maximum number of courses we can complete within their deadlines.
Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.
Solution Approach
The solution takes a greedy approach along with the use of a priority queue to maximize the number of courses taken. Here, we go through the algorithm and patterns used in the solution:
-
Sorting: Initially, we sort the
courses
array by their deadlines, which islastDay_i
for thei-th
course. This is done to prioritize courses with the earliest deadlines, allowing us to take courses in a sequence that respects those deadlines.1courses.sort(key=lambda x: x[1])
-
Priority Queue (Min-Heap): We use a priority queue (min-heap) to keep track of the courses we have decided to take. Since Python's
heapq
library only supports a min-heap and we want to have the functionality of a max-heap (to easily pop the longest course when needed), we store negative durations in the heap.The priority queue (heap) operations used are:
heappush
to add an element to the heapheappop
to remove the smallest element, which in our case will be the course with the longest duration due to the negation
1pq = []
-
Iterating Through the Courses: We iterate through the sorted
courses
list, and for each course, we perform the following steps:a. First, we push the negative duration of the current course onto the heap and add the duration to an accumulator
s
.1 ```python 2 heappush(pq, -duration) 3 s += duration 4 ```
b. Then, we check if adding the current course has caused the total duration (
s
) to exceed the last day by which the course must be completed. If it does, we enter a while loop:1 - Inside the loop, we pop the course with the longest duration (which is at the top of the heap due to being the smallest negative number), and subtract from our total duration `s`. 2 3 - We continue this process until the total duration `s` no longer exceeds the deadline of the current course or until the heap is empty. 4 5 ```python 6 while s > last: 7 s += heappop(pq) 8 ```
-
Count of Courses Taken: After iterating through all courses and adjusting our schedule as necessary, the remaining courses in the heap represent the courses that we can complete within their respective deadlines. Hence, the length of the heap gives us the maximum number of courses that can be taken.
1return len(pq)
By using the greedy strategy of always picking the next course that can be finished before its deadline after the courses already scheduled, and by adjusting the schedule when necessary by dropping the longest course, the algorithm ensures we optimize for the maximum number of courses taken.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach, let's use a small example of the courses array:
1courses = [[100, 200], [70, 150], [120, 210]]
-
Sorting by Deadlines
First, we sort the courses by their deadlines:
courses.sort(key=lambda x: x[1])
After sorting:
1courses = [[70, 150], [100, 200], [120, 210]]
Now, our courses array is sorted by the last day on which the courses need to be completed, enabling us to focus on the courses with the earliest deadlines first.
-
Initializing the Priority Queue
We create a priority queue (min-heap) to help us keep track of the courses we're taking.
pq = []
Initially, the priority queue is empty.
-
Iterating Through the Courses
We go through each course and follow a series of steps.
a. For the first course
[70, 150]
:- We add the negative course duration to the heap and update the accumulator,
s
:1heappush(pq, -70) 2s = 70
b. The total duration
s
does not exceed the last day of the current course (150), so we move to the next course.a. For the second course
[100, 200]
:- We add the negative course duration to the heap and update the accumulator,
s
:1heappush(pq, -100) 2s = 170
b. The total duration
s
does not exceed the last day of the current course (200), so we move to the next course.a. For the third course
[120, 210]
:- We add the negative course duration to the heap and update the accumulator,
s
:1heappush(pq, -120) 2s = 290
b. Now the total duration
s
exceeds the last day of the current course (210). We need to adjust our schedule:-
We keep removing the longest duration courses from the pile (the one with the least negative value) until
s
is less than or equal to the deadline:1s += heappop(pq) # Removes -120, adding it back to s gives s = 290 - 120 = 170
-
As
s
is now 170, it still exceeds the deadline for the course, so we continue the process:1s += heappop(pq) # This time, removes -100, updating s to s = 170 - 100 = 70
-
Now, with
s
equal to 70, it does not exceed the deadline for the third course, so we can stop adjusting the schedule.
- We add the negative course duration to the heap and update the accumulator,
-
Count of Courses Taken:
After iterating through all the courses and adjusting the schedule, the number of courses left in the queue is the number we can complete within their respective deadlines. So the final answer is:
return len(pq)
Since the heap now contains only the first course
[-70]
, we get the final result:1Maximum number of courses = 1
This example highlights the greedy decision-making process: by sorting the courses by deadlines and using a priority queue to manage durations, dropping the longest course if the total duration exceeds a course's deadline, we optimize for the maximum number of courses that can be completed.
Solution Implementation
1from heapq import heappush, heappop
2
3class Solution:
4 def scheduleCourse(self, courses: List[List[int]]) -> int:
5 # Sort the courses based on their end day
6 courses.sort(key=lambda x: x[1])
7
8 # Initialize a max heap to keep track of the longest courses we have taken
9 max_heap = []
10
11 # This variable will hold the total duration of all courses we have taken so far
12 total_duration = 0
13
14 # Iterate over each course
15 for duration, last_day in courses:
16 # Add the current course to the max heap and increment the total duration
17 heappush(max_heap, -duration)
18 total_duration += duration
19
20 # If the total duration exceeds the last day of the current course,
21 # remove the longest course from our schedule
22 while total_duration > last_day:
23 # heappop returns a negative number because we are using max heap,
24 # so we add it back to reduce the total duration
25 total_duration += heappop(max_heap)
26
27 # The number of courses in the max heap is the number of courses we can take
28 return len(max_heap)
29
1class Solution {
2 public int scheduleCourse(int[][] courses) {
3 // Sort the courses by their end day
4 Arrays.sort(courses, (course1, course2) -> course1[1] - course2[1]);
5
6 // Create a max-heap (priority queue) to keep track of the longest courses taken so far
7 PriorityQueue<Integer> maxHeap = new PriorityQueue<>((duration1, duration2) -> duration2 - duration1);
8
9 int currentTime = 0; // Keep track of the total duration of all courses taken so far
10
11 // Iterate through each course
12 for (int[] course : courses) {
13 // Extract the course duration and the last day the course can be taken
14 int duration = course[0], lastDay = course[1];
15
16 // Add the current course duration to the heap and increment total time
17 maxHeap.offer(duration);
18 currentTime += duration;
19
20 // If the current time exceeds the end day of the last course, remove the longest course duration
21 while (currentTime > lastDay) {
22 currentTime -= maxHeap.poll(); // This keeps us within the last day limit
23 }
24 }
25
26 // The size of the heap indicates the maximum number of courses that can be taken
27 return maxHeap.size();
28 }
29}
30
1#include <vector>
2#include <algorithm> // for std::sort
3#include <queue> // for std::priority_queue
4
5class Solution {
6public:
7 int scheduleCourse(vector<vector<int>>& courses) {
8 // Sort the input vector of courses by their end days using a custom comparator.
9 sort(courses.begin(), courses.end(), [](const vector<int>& courseA, const vector<int>& courseB) {
10 return courseA[1] < courseB[1];
11 });
12
13 // Use a max-heap (priority queue) to keep track of the longest courses taken.
14 priority_queue<int> maxHeap;
15 int totalTime = 0; // This will accumulate the total time taken by selected courses.
16
17 // Iterate through each course in the sorted course list.
18 for (auto& course : courses) {
19 int duration = course[0]; // Duration of the current course.
20 int deadline = course[1]; // Deadline (last day) of the current course.
21
22 // Add the duration to the total time and push it onto the max-heap.
23 maxHeap.push(duration);
24 totalTime += duration;
25
26 // If the total time exceeds the current course's deadline,
27 // remove the longest course from the total time and the max-heap.
28 // Repeat this process to ensure we stay within the deadline.
29 while (totalTime > deadline) {
30 totalTime -= maxHeap.top();
31 maxHeap.pop();
32 }
33 }
34
35 // The number of courses in the max-heap gives us the maximum number of courses
36 // that can be taken without exceeding their respective deadlines.
37 return maxHeap.size();
38 }
39};
40
1// Importing the MaxPriorityQueue from a library such as 'typescript-collections'
2import { MaxPriorityQueue } from 'typescript-collections';
3
4/**
5 * Finds the maximum number of courses that can be taken given the duration and last day to finish each course.
6 * @param courses - An array of pairs [duration, lastDay], where duration represents how long the course takes to complete,
7 * and lastDay represents the last day the course can be finished.
8 * @returns The maximum number of courses that can be taken.
9 */
10function scheduleCourse(courses: number[][]): number {
11 // Sorts courses based on their ending time in ascending order
12 courses.sort((a, b) => a[1] - b[1]);
13
14 // Initialize a Max Priority Queue to manage the durations of the courses taken
15 const priorityQueue = new MaxPriorityQueue<number>();
16
17 // Represents the current accumulated duration of all selected courses
18 let totalDuration = 0;
19
20 // Iterate through each course
21 for (const [duration, lastDay] of courses) {
22 // Insert current course duration into the priority queue
23 priorityQueue.enqueue(duration);
24
25 // Add the current course's duration to the total duration
26 totalDuration += duration;
27
28 // If the total duration exceeds the current course's last day,
29 // remove the course with the longest duration to meet the deadline
30 while (totalDuration > lastDay) {
31 totalDuration -= priorityQueue.dequeue().element;
32 }
33 }
34
35 // At this point, the priority queue contains the maximum number of courses that fit within their deadlines
36 return priorityQueue.size();
37}
38
39// Note: You must include the appropriate library for the MaxPriorityQueue.
40// The 'typescript-collections' library is assumed in this example, but you
41// might be using a different one, so adjust imports accordingly.
42
Time and Space Complexity
The time complexity of the above code is O(n log n)
for sorting the courses, where n
is the number of courses. The insertion and deletion operations in the priority queue take O(log k)
, where k
is the number of courses currently in the queue. Since each course can be pushed onto and popped from the queue once, in the worst case the total cost for these operations is O(n log k)
. Assuming the queue could have at most n
courses, the total time complexity of the algorithm becomes O(n log n)
due to the initial sort dominating the overall complexity.
The space complexity of the code is O(n)
which is due to the priority queue storing at most n
courses at any time.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement recursion?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.