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.

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:

  1. Sorting: Initially, we sort the courses array by their deadlines, which is lastDay_i for the i-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])
  2. 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 heap
    • heappop to remove the smallest element, which in our case will be the course with the longest duration due to the negation
    1pq = []
  3. 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 ```
  4. 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.

💪
Level Up Your
Algo Skills

Example Walkthrough

To illustrate the solution approach, let's use a small example of the courses array:

1courses = [[100, 200], [70, 150], [120, 210]]
  1. 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.

  2. 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.

  3. 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.

  4. 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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫