Solution: Course Schedule III
Tags: algorithms, javascript, java, python
Published: 2021-05-02 10:42:59

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/course-schedule-iii/discuss/1187504).*

---

#### [Leetcode Problem #630 (*Hard*): Course Schedule III](https://leetcode.com/problems/course-schedule-iii/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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:<br><br>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.<br><br>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.<br><br>Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day.<br><br>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:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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();
    }
};
```