Leetcode 630. Course Schedule III

Problem Explanation:

This problem is about scheduling online courses efficiently in order to maximize the number of courses taken. Every course has a duration which is the amount of days it needs for completion and a deadline, the day it will be closed. Assuming that we start courses on the first day and must complete each course before its deadline, our task is to find the maximum number of courses that can be attended.

One note is that courses can't be taken simultaneously. In other words, at any moment, only one course should be under progress.

The problem can be illustrated using the example below:

Input: arr[] = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] Output: 3

Explanation: Here we have 4 courses. The first course will take 100 days to finish which is before its deadline, the 200th day. On the 101st day, you can start the third course, which will be finished on the 1100th day, just before its deadline, the 1250th day. The next day (1101st), you can take the second course and finish it on the 1300th day which is its deadline. But you can't take the fourth course as it will be finished on the 3300 day which is later than its deadline (3200th day)

To ensure maximum efficiency, we can use a priority queue to store the durations of the courses, and a greedy algorithm concept to ensure that we take the courses with the shortest durations as priority.

Python Solution:

1
2python
3import heapq
4class Solution:
5    def scheduleCourse(self, courses: List[List[int]]) -> int:
6        # Sort the courses by their deadlines
7        courses.sort(key=lambda x: x[1])
8
9        # Create a max heap to store the duration of courses
10        maxHeap = []
11        # Initialize the current time to zero
12        curr_time = 0
13
14        for t, end in courses:
15            curr_time += t
16            # Push the duration to max heap
17            heapq.heappush(maxHeap, -t)
18            while curr_time > end:
19                # If the current time exceeds the course end time, we pop out a course with largest duration
20                curr_time += heapq.heappop(maxHeap)
21        return len(maxHeap)

Java Solution:

1
2java
3class Solution {
4    public int scheduleCourse(int[][] courses) {
5        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
6        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
7        int time = 0;
8        for (int[] course: courses) {
9            time += course[0];
10            queue.add(course[0]);
11            if (time > course[1]) {
12                time -= queue.poll();
13            }
14        }
15        return queue.size();
16    }
17}

C++ Solution:

1
2c++
3class Solution {
4public:
5    int scheduleCourse(vector<vector<int>>& courses) {
6        sort(courses.begin(), courses.end(), [](vector<int>& a, vector<int>& b) {
7            return a[1] < b[1];
8        });
9        priority_queue<int> maxHeap;
10        int time = 0;
11        for (vector<int>& course: courses) {
12            int duration = course[0];
13            int end = course[1];
14            time += duration;
15            maxHeap.push(duration);
16            if (time > end) {
17                time -= maxHeap.top();
18                maxHeap.pop();
19            }
20        }
21        return maxHeap.size();
22    }
23};

C# Solution:

1
2csharp
3public class Solution {
4    public int ScheduleCourse(int[][] courses) {
5        var sortedCourses = courses.OrderBy(x => x[1]).ToArray();
6        var heap = new SortedSet<int>(Comparer<int>.Create((x, y) => x == y ? 1 : x.CompareTo(y)));
7        int time = 0;
8        foreach (var course in sortedCourses) {
9            heap.Add(course[0]);
10            time += course[0];
11            if (time > course[1]) {
12                time -= heap.Max;
13                heap.Remove(heap.Max);
14            }
15        }
16        return heap.Count;
17    }
18}

JavaScript Solution:

1
2javascript
3var scheduleCourse = function(courses) {
4    // Sort by end date
5    courses.sort((a, b) => a[1] - b[1]);
6
7    // Priority (max) heap based on course duration
8    const durations = new PriorityQueue((a, b) => a > b);
9    
10    let currentTime = 0;
11
12    for (let [duration, lastDay] of courses) {
13        if (currentTime + duration <= lastDay) {
14            // If we can finish the course before it ends
15            durations.add(duration);
16            currentTime += duration;
17        } else if (durations.peek() > duration) {
18            // We can't finish the course before it ends
19            // But if the current course is shorter than the longest course we're taken
20            // We can replace the longest course with the current one for more spare days
21            currentTime += duration - durations.poll();
22            durations.add(duration);
23        }
24    }
25
26    return durations.size();
27};

Note: In JavaScript solution, a PriorityQueue( )function is used which is not a built-in function in JavaScript. You need to implement or import this function.In JavaScript, you could also utilize some performance optimized inbuilt functions like sort and pop which can make your code simpler and easy to understand. Here's how you should implement it using JavaScript by including a heapify-down process and using the built-in sort function.

Simpler Javascript Solution :

1
2javascript
3function scheduleCourse(courses) {
4    // sort courses by ending day
5    courses.sort((a, b) => a[1] - b[1]);
6
7    let totalDays = 0;
8    let maxHeap = [];
9    for (let course of courses) {
10        totalDays += course[0];
11        // Heapify Up Process
12        maxHeap.unshift(course[0]);
13        maxHeap.sort((a, b) => b - a);
14        // Heapify Down Process
15        while (totalDays > course[1]) {
16            totalDays -= maxHeap.shift();
17        }
18    }
19    return maxHeap.length;
20}

This solution works by sorting the courses by end date and then adding each course to a max heap that manages the accumulated total time. Whenever the total time surpasses the end time, the algorithm removes the most time-consuming course from the list (using shift). As a result, we can always guarantee that we're doing the most courses possible at any point in time.

This solution also uses JavaScript's built-in sort function and shift function which removes from the beginning of an array. The shift function works well here because we've built our max heap using an array in such a way that the first element is always the largest. This makes it easy to remove this element when we need to lower our total course time. With these properties, we can remove the most time consuming course easily.

When all courses have been examined, the resulting size of the max heap will be the maximum number of courses that can be taken before their respective deadlines.