Course Schedule III

Problem

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 1^st day and you cannot take two or more courses simultaneously.

Return the maximum number of courses that you can take.

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 1^st course, it costs 100 days so you will finish it on the 100^th day, and ready to take the next course on the 101^st day.
Second, take the 3^rd course, it costs 1000 days so you will finish it on the 1100^th day, and ready to take the next course on the 1101^st day. 
Third, take the 2^nd course, it costs 200 days so you will finish it on the 1300^th day. 
The 4^th course cannot be taken now, since you will finish it on the 3300^th 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⁴
1 <= duration_i, lastDay_i <= 10⁴

Solution

/**
 * @param {number[][]} courses
 * @return {number}
 */
var scheduleCourse = function(courses) {
    courses.sort((a, b) => a[1] - b[1]); // sort by deadline
    const maxHeap = new MaxPriorityQueue(); // max-heap by duration of courses we will take
    let time = 0; // current time if complete duration in heap (ie. sum of maxHeap values)

    for (const [duration, lastDay] of courses) {
        if (time + duration <= lastDay) { // can finish current course
            maxHeap.enqueue(duration);
            time += duration;
        } else if (maxHeap.front()?.element > duration) { // take course with shorter duration
            time += duration - maxHeap.dequeue().element;
            maxHeap.enqueue(duration);
        }
    }
    return maxHeap.size();
};

We will implement a greedy solution. We sort courses by their deadline in ascending order, and create a max-heap maxHeap that uses the course duration as the priority (the course in maxHeap are course we will take). Next, as we iterate through courses, if a course can be taken (ie. time + duration doesn't exceed lastDay), we push it into maxHeap.

Notice that all courses in maxHeap have deadlines before our current course since courses is sorted by deadline in ascending order (ie. all previous courses that we gone through have earlier deadlines). This means that if we can't take the current course, and the current course has duration less than the top of maxHeap (ie. the course we are taking that has the greatest duration), we can choose to take our current course instead.

Furthermore, this is actually what we want, as it minimizes time, while the number of courses in maxHeap doesn't change. Thus, since time is minimized, there is more leeway to take other courses, which maximizes the number of courses we can take.

Problem​

Solution​

Problem

Solution