seanpgallivan

Posted on

Solution: Course Schedule III

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

There are `n` different online courses numbered from `1` to `n`. You are given an array `courses` where `courses[i] = [duration<i>, lastDay<i>]` indicate that the `i'th` course should be taken continuously for `duration<i>` days and must be finished before or on `lastDay<i>`.

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.

Examples:

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 <= 10^4`
• `1 <= durationi, lastDayi <= 10^4`

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

If we think of this problem in a larger sense, we can envision a slightly more simplistic situation without the issues of the last day cutoff for each course. In that scenario, we could quite easily add up all the course durations, then selectively remove the courses with the longest remaining duration until we've found the ideal number of courses that will fit into our desired timeframe.

The trouble here, of course, is that we do have cutoffs for each course, which means we can no longer fill the entire time before removing courses. Instead, we'll have to selectively backtrack and remove courses as we iterate through the input array (C).

As is often the case in a scheduling-type problem, this leads to a particular issue: we'll want to sort the data in two distinctly different ways. Since we'll be progressing through C as if we're progressing through time, we'll want to sort C based on the courses' cutoffs (end), but when we backtrack to potentially remove a course, we'll want to sort the courses we've accepted by their duration (dur).

The need for a data structure that will maintain its sort through insertions and max value removals means that we're looking for a max priority queue or max-heap.

Once we've sorted C and set up our max priority queue or heap (pq/heap), it's simply a matter of iterating through C, adding the courses to pq/heap, and then removing the max duration course as necessary to stay underneath the current end value with our accumulated duration (total).

In order to minimize unnecessary insertions/removals, we can perform a few basic conditional checks to tell if they're necessary. If the current course will already fit, we can just add it, or if the current course is a better fit than our longest course, then we can swap them.

Then, once we reach the end of C, pq/heap should contain all the non-discarded courses, so we can return its size as our answer.

• Time Complexity: O(N * log N) where N is the length of C, due to both the sort and the priority queue / heap implementation
• Space Complexity: O(N) due to the priority queue / heap data

Implementation:

In this instance, the MaxPriorityQueue() npm for Javascript was actually competitively performant compared to a custom max-heap structure.

To avoid having to use a custom comparator for Python, which defaults to a min heap, we can just switch the sign before insertion and after extraction to mimic a max heap.

Javascript Code:

``````var scheduleCourse = function(C) {
C.sort((a,b) => a[1] - b[1])
let total = 0, pq = new MaxPriorityQueue({priority: x => x})
for (let [dur, end] of C)
if (dur + total <= end)
total += dur, pq.enqueue(dur)
else if (pq.front() && pq.front().element > dur)
total += dur - pq.dequeue().element, pq.enqueue(dur)
return pq.size()
};
``````

Python Code:

``````class Solution:
def scheduleCourse(self, C: List[List[int]]) -> int:
heap, total = [], 0
for dur, end in sorted(C, key=lambda el: el[1]):
if dur + total <= end:
total += dur
heappush(heap, -dur)
elif heap and -heap[0] > dur:
total += dur + heappop(heap)
heappush(heap, -dur)
return len(heap)
``````

Java Code:

``````class Solution {
public int scheduleCourse(int[][] C) {
Arrays.sort(C, (a,b) -> a[1] - b[1]);
PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);
int total = 0;
for (int[] course : C) {
int dur = course[0], end = course[1];
if (dur + total <= end) {
total += dur;
} else if (pq.size() > 0 && pq.peek() > dur) {
total += dur - pq.poll();
}
}
return pq.size();
}
}
``````

C++ Code:

``````class Solution {
public:
int scheduleCourse(vector<vector<int>>& C) {
sort(C.begin(), C.end(), [](auto &a, auto &b) {return a[1] < b[1];});
priority_queue<int> pq;
int total = 0;
for (auto &course : C) {
int dur = course[0], end = course[1];
if (dur + total <= end)
total += dur, pq.push(dur);
else if (pq.size() && pq.top() > dur)
total += dur - pq.top(), pq.pop(), pq.push(dur);
}
return pq.size();
}
};
``````