Code Implementation

import heapq

class Solution:
    def scheduleCourse(self, courses):
        # Sort courses by their end day (lastDay)
        courses.sort(key=lambda x: x[1])
        total_time = 0
        max_heap = []
        
        for duration, lastDay in courses:
            total_time += duration
            heapq.heappush(max_heap, -duration)  # use negative for max-heap
            if total_time > lastDay:
                # Remove the longest course to stay within the deadline
                total_time += heapq.heappop(max_heap)
        return len(max_heap)
      

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(courses.begin(), courses.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        priority_queue<int> maxHeap;
        int totalTime = 0;
        for (const auto& c : courses) {
            totalTime += c[0];
            maxHeap.push(c[0]);
            if (totalTime > c[1]) {
                totalTime -= maxHeap.top();
                maxHeap.pop();
            }
        }
        return maxHeap.size();
    }
};
      

import java.util.*;

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int totalTime = 0;
        for (int[] c : courses) {
            totalTime += c[0];
            maxHeap.add(c[0]);
            if (totalTime > c[1]) {
                totalTime -= maxHeap.poll();
            }
        }
        return maxHeap.size();
    }
}
      

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    push(val) {
        this.heap.push(val);
        this._siftUp();
    }
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._siftDown();
        return max;
    }
    size() {
        return this.heap.length;
    }
    _siftUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            let parent = Math.floor((idx - 1) / 2);
            if (this.heap[parent] >= this.heap[idx]) break;
            [this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
            idx = parent;
        }
    }
    _siftDown() {
        let idx = 0;
        const length = this.heap.length;
        while (true) {
            let left = 2 * idx + 1, right = 2 * idx + 2, largest = idx;
            if (left < length && this.heap[left] > this.heap[largest]) largest = left;
            if (right < length && this.heap[right] > this.heap[largest]) largest = right;
            if (largest === idx) break;
            [this.heap[largest], this.heap[idx]] = [this.heap[idx], this.heap[largest]];
            idx = largest;
        }
    }
}

var scheduleCourse = function(courses) {
    courses.sort((a, b) => a[1] - b[1]);
    let totalTime = 0;
    let maxHeap = new MaxHeap();
    for (let [duration, lastDay] of courses) {
        totalTime += duration;
        maxHeap.push(duration);
        if (totalTime > lastDay) {
            totalTime -= maxHeap.pop();
        }
    }
    return maxHeap.size();
};
      

Problem Description

You are given a list of courses, where each course is represented as a pair [duration, lastDay]:

• duration is the number of days required to complete the course
• lastDay is the last day by which the course must be finished

• Each course can be taken at most once.
• Once you start a course, you must finish it before starting another.
• There may be multiple valid solutions; you want the maximum number of courses.

The input is a list of courses where each element is [duration, lastDay]. Return the maximum number of courses you can take.

Thought Process

At first glance, this problem seems similar to scheduling or interval problems. One might think of trying every possible order of taking courses, but that would be inefficient since the number of combinations grows rapidly as the number of courses increases.

The naive approach would be to try all possible subsets and orders, but this is computationally infeasible for large inputs.

Instead, we need to find a way to optimize our choices. Since we want to take as many courses as possible, it makes sense to:

• Prefer courses that end earlier, so we have more time left for others.
• Drop the most "expensive" (longest) course if we ever exceed a deadline, to try and fit more courses overall.

Solution Approach

• Step 1: Sort Courses by Deadline
  First, sort the courses by their lastDay. This ensures that we always consider the tightest deadlines first, which helps in maximizing the number of courses.
• Step 2: Use a Max Heap to Track Durations
  As we iterate through the sorted courses, we maintain a running sum total_time of the durations of the courses we've chosen so far.
  We also use a max heap (priority queue) to keep track of the durations of the courses we've selected. This allows us to efficiently remove the course with the longest duration if adding a new course causes us to exceed its deadline.
• Step 3: Iterate and Decide
  For each course:
  • Add its duration to total_time and push its duration to the max heap.
  • If total_time exceeds the current course's lastDay, we remove the course with the largest duration from our selection (pop from the max heap) and subtract its duration from total_time. This step helps us "make room" for more courses by dropping the most time-consuming one.
• Step 4: The Result
  At the end, the number of courses in the max heap is the maximum number of courses we can take.

The heap is crucial because it lets us efficiently keep our schedule as tight as possible, always prioritizing shorter courses if we need to make room.

Example Walkthrough

Sample Input: courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]

1. Sort by lastDay:
   [[100, 200], [1000, 1250], [200, 1300], [2000, 3200]]
2. Take [100, 200]:
   • total_time = 100
   • Within deadline (100 ≤ 200). Heap: [100]
3. Take [1000, 1250]:
   • total_time = 1100
   • Within deadline (1100 ≤ 1250). Heap: [1000, 100]
4. Take [200, 1300]:
   • total_time = 1300
   • Within deadline (1300 ≤ 1300). Heap: [1000, 100, 200]
5. Take [2000, 3200]:
   • total_time = 3300
   • Exceeds deadline (3300 > 3200). Remove course with largest duration (1000). Heap after removal: [200, 100, 2000]. total_time = 2300
   • Now within deadline.
6. Result: 3 courses taken (the heap size).

This process shows how we always make room for more courses by dropping the most time-consuming one when necessary.

Time and Space Complexity

• Brute-force Approach:
  Trying every possible subset and order of courses is O(n!) (factorial time), which is infeasible for large n.
• Optimized Approach:
  
  • Sorting the courses: O(n \log n)
  • Each course is pushed and possibly popped from the heap once: O(n \log n)
  • Overall time complexity: O(n \log n)
  • Space complexity: O(n) for the heap (in the worst case, all courses are taken)

The use of a heap ensures that both adding and removing courses is efficient, and sorting up front keeps our schedule as tight as possible.

Summary

The key insight for Course Schedule III is to always try to fit courses with earlier deadlines first, and to use a max heap to efficiently "swap out" the most time-consuming course when necessary. This greedy approach, combined with efficient data structures, allows us to maximize the number of courses we can attend without violating any deadlines. The elegance of the solution comes from reducing a complex scheduling problem to a simple process of sorting and heap management.