Course Schedule III

Problem Statement

In this task, you're provided with a list of online courses, each characterized by its duration and the latest completion day. Specifically, each entry in the courses array courses[i] = [durationi, lastDayi] describes a course that requires durationi days to complete and must be wrapped up on or before lastDayi. Beginning on day 1, and without the ability to undertake multiple courses simultaneously, the challenge is to figure out the maximum number of courses you can complete.

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 <= 104
• 1 <= durationi, lastDayi <= 104

Approach and Intuition

Given the structure of this problem, we can use a strategy similar to interval scheduling optimization where we aim to maximize the number of intervals (courses) that don't overlap. However, instead of directly tackling the course durations and deadlines as intervals, we need a prioritized approach determined by the course deadlines to ensure we're not only completing courses but also doing so within their stipulated time frame. Here's a stepped breakdown of how to approach this:

1. Sorting for Priority: Start by organizing the courses based on their deadline (lastDayi). This allows you to process the courses in the order of urgency, considering their last valid completion day.

2. Using a Priority Queue: As you iterate through the organized courses, maintain a max-heap (priority queue) where you keep track of the course durations. This heap helps manage the courses you have decided to take by keeping the longest durations at the top.

3. Decision Making with Heap: For each course:

   • Add the current course’s duration to a running total (currentTime).
   • If currentTime exceeds the course’s last day (lastDayi), it indicates that you cannot finish this course by the deadline even if it's the last course to start by its deadline. To handle this, you should ideally drop the course that takes the longest time (which will be at the top of the heap) to make room for potential shorter courses that could fit in the schedule.

4. Final Count: The size of your heap (priority queue) after processing all courses will represent the maximum number of courses you can complete within their respective deadlines.

This approach effectively balances the courses’ urgency (deadline) and their duration, ensuring you take the maximum number of courses in an auditable manner keeping the deadlines in check.

Solutions

public class Solution {
    public int manageCourses(int[][] courseList) {
        Arrays.sort(courseList, (x, y) -> x[1] - y[1]);
        PriorityQueue < Integer > maxHeap = new PriorityQueue < > ((x, y) -> y - x);
        int totalTime = 0;
        for (int[] course: courseList) {
            if (totalTime + course[0] <= course[1]) {
                maxHeap.offer(course[0]);
                totalTime += course[0];
            } else if (!maxHeap.isEmpty() && maxHeap.peek() > course[0]) {
                totalTime += course[0] - maxHeap.poll();
                maxHeap.offer(course[0]);
            }
        }
        return maxHeap.size();
    }
}