Course Schedule III

This is the most efficient approach, employing a greedy strategy. We process courses sorted by their deadlines. We tentatively take each course if possible. If taking a course violates its deadline, we check if we can swap it with a previously taken course that has a longer duration. This swap reduces the total time spent, potentially allowing us to take more courses overall.

• Sort the courses array based on lastDay in ascending order.
• Initialize a max-priority queue, pq, to store the durations of courses taken.
• Initialize currentTime = 0.
• For each course [duration, lastDay] in the sorted list:
  • If currentTime + duration <= lastDay:
    • Add the course: currentTime += duration, pq.offer(duration).
  • Else if the priority queue is not empty and its top element (max duration) is greater than the current duration:
    • Swap the courses: currentTime = currentTime - pq.poll() + duration, pq.offer(duration).
• Return the size of the priority queue.

The optimal strategy involves a greedy choice. First, we sort the courses by their lastDay. This ensures we prioritize courses that need to be finished earlier. We iterate through these sorted courses, maintaining a currentTime which tracks the total duration of courses taken so far.

For each course, we check if we can add it to our schedule. If currentTime + course.duration <= course.lastDay, it fits perfectly. We add its duration to currentTime and add the duration to a max-priority queue. The priority queue will store the durations of all the courses we've decided to take.

If the course doesn't fit (currentTime + course.duration > course.lastDay), we have a conflict. We can't simply add it. However, we can check if it's beneficial to swap this current course with one we've already taken. To make the schedule more flexible for future courses, we want to minimize the currentTime. This can be achieved by replacing the longest course taken so far with the current course, but only if the current course is shorter. We use the max-priority queue to find the longest course taken so far (its peek()). If pq.peek() > course.duration, we perform the swap: remove the max duration from pq and currentTime, and add the current course's duration instead. This reduces the total time and makes the schedule valid for the current course, while keeping the number of courses taken the same.

After iterating through all courses, the size of the priority queue gives the maximum number of courses we could take.

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, Comparator.comparingInt(a -> a[1]));
        
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int currentTime = 0;
        
        for (int[] course : courses) {
            int duration = course[0];
            int lastDay = course[1];
            
            if (currentTime + duration <= lastDay) {
                currentTime += duration;
                pq.offer(duration);
            } else if (!pq.isEmpty() && pq.peek() > duration) {
                currentTime += duration - pq.poll();
                pq.offer(duration);
            }
        }
        
        return pq.size();
    }
}