630. Course Schedule III

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

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.

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 2nd course, it costs 200 days so you will finish it on the 300th day, and ready to take the next course on the 301st day. 
Third, take the 3rd course, it costs 1000 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 ≤ 10⁴
1 ≤ duration_i, lastDay_i ≤ 10⁴

Python Solution

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda x: x[1])  # Sort by end time
        heap = []  # Max heap to store durations
        time = 0
        
        for duration, end in courses:
            time += duration
            heapq.heappush(heap, -duration)  # Push negative for max heap
            
            if time > end:  # If current schedule exceeds deadline
                # Remove the longest course
                time += heapq.heappop(heap)
                
        return len(heap)

Alternative Solution (Using Priority Queue):

from queue import PriorityQueue

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda x: x[1])
        pq = PriorityQueue()
        time = 0
        
        for duration, end in courses:
            time += duration
            pq.put(-duration)  # Negative for max priority queue
            
            if time > end:
                time += pq.get()  # Remove longest course
                
        return pq.qsize()

Implementation Notes:

Time Complexity: O(n log n) for sorting and heap operations
Space Complexity: O(n) for the heap
Uses greedy approach with priority queue
Maintains running time and removes longest course when needed

Java Solution

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        PriorityQueue pq = new PriorityQueue<>((a, b) -> b - a);
        int time = 0;
        
        for (int[] course : courses) {
            time += course[0];
            pq.offer(course[0]);
            
            if (time > course[1]) {
                time -= pq.poll();
            }
        }
        
        return pq.size();
    }
}

Alternative Solution (Using TreeSet):

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        TreeSet taken = new TreeSet<>();
        int time = 0;
        int index = 0;
        
        for (int[] course : courses) {
            if (time + course[0] <= course[1]) {
                time += course[0];
                taken.add(index);
            } else if (!taken.isEmpty() && 
                courses[taken.last()][0] > course[0]) {
                time += course[0] - courses[taken.last()][0];
                taken.remove(taken.last());
                taken.add(index);
            }
            index++;
        }
        
        return taken.size();
    }
}

C++ Solution

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

Alternative Solution (Using multiset):

class Solution {
public:
    int scheduleCourse(vector>& courses) {
        sort(courses.begin(), courses.end(),
             [](const vector& a, const vector& b) {
                 return a[1] < b[1];
             });
        
        multiset taken;
        int time = 0;
        
        for (const auto& course : courses) {
            if (time + course[0] <= course[1]) {
                time += course[0];
                taken.insert(course[0]);
            } else if (!taken.empty() && 
                      *taken.rbegin() > course[0]) {
                time += course[0] - *taken.rbegin();
                taken.erase(prev(taken.end()));
                taken.insert(course[0]);
            }
        }
        
        return taken.size();
    }
};

JavaScript Solution

/**
 * @param {number[][]} courses
 * @return {number}
 */
var scheduleCourse = function(courses) {
    courses.sort((a, b) => a[1] - b[1]);
    const heap = new MaxHeap();
    let time = 0;
    
    for (const [duration, end] of courses) {
        time += duration;
        heap.push(duration);
        
        if (time > end) {
            time -= heap.pop();
        }
    }
    
    return heap.size();
};

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

C# Solution

public class Solution {
    public int ScheduleCourse(int[][] courses) {
        Array.Sort(courses, (a, b) => a[1].CompareTo(b[1]));
        var pq = new PriorityQueue();
        int time = 0;
        
        foreach (var course in courses) {
            time += course[0];
            pq.Enqueue(course[0], -course[0]);  // Negative for max priority
            
            if (time > course[1]) {
                time -= pq.Dequeue();
            }
        }
        
        return pq.Count;
    }
}

Alternative Solution (Using SortedSet):

public class Solution {
    public int ScheduleCourse(int[][] courses) {
        Array.Sort(courses, (a, b) => a[1].CompareTo(b[1]));
        var taken = new SortedSet<(int duration, int index)>();
        int time = 0;
        
        for (int i = 0; i < courses.Length; i++) {
            if (time + courses[i][0] <= courses[i][1]) {
                time += courses[i][0];
                taken.Add((courses[i][0], i));
            } else if (taken.Count > 0 && 
                      taken.Max.duration > courses[i][0]) {
                time += courses[i][0] - taken.Max.duration;
                taken.Remove(taken.Max);
                taken.Add((courses[i][0], i));
            }
        }
        
        return taken.Count;
    }
}

Implementation Notes:

Both solutions use different data structures for optimization
PriorityQueue solution is more straightforward and efficient
SortedSet solution provides additional functionality for complex scenarios
Time complexity remains O(n log n) for both approaches