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.
Leetcode Problem #630 (Hard): Course Schedule III
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
There are
ndifferent online courses numbered from1ton. You are given an arraycourseswherecourses[i] = [duration<i>, lastDay<i>]indicate that thei'thcourse should be taken continuously forduration<i>days and must be finished before or onlastDay<i>.You will start on the
1stday 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^41 <= 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:
(Jump to: Problem Description || Solution Idea)
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:
(Jump to: Problem Description || Solution Idea)
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:
(Jump to: Problem Description || Solution Idea)
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;
pq.add(dur);
} else if (pq.size() > 0 && pq.peek() > dur) {
total += dur - pq.poll();
pq.add(dur);
}
}
return pq.size();
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
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();
}
};
Top comments (1)
A great way of explaining, wish you could explain it more easier way. Anyways, thank you.