Course Schedule III

Hard
1427.

Course Schedule III

Course Schedule III is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.

There are n online courses. Course i is courses[i] = [duration, lastDay]: it takes duration consecutive days and must be finished on or before day lastDay.

You start on day 1 and can study only one course at a time; a course taken from day s occupies days s through s + duration - 1. Courses you skip cost nothing.

Return the maximum number of courses you can complete.

Example 1

Input
courses = [[3,5],[2,4],[4,9],[5,9]]
Output
3
Explanation
Take the 2-day course (done day 2), the 3-day one (done day 5) and the 4-day one (done day 9). All four would need 14 days.

Example 2

Input
courses = [[1,2]]
Output
1

Example 3

Input
courses = [[3,2],[4,3]]
Output
0
Explanation
Neither course fits before its own deadline.

Constraints

  • 1 <= courses.length <= 10^4
  • 1 <= duration, lastDay <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} courses
 * @return {number}
 */
var scheduleCourse = function(courses) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Course Schedule III — Solution in Python, Java & C++

Course Schedule III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and sorting.

Course Schedule III is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Hard
  • Topics: Arrays, Sorting, Greedy, Heap
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

There are n online courses. Course i is courses[i] = [duration, lastDay]: it takes duration consecutive days and must be finished on or before day lastDay.

You start on day 1 and can study only one course at a time; a course taken from day s occupies days s through s + duration - 1. Courses you skip cost nothing.

Return the maximum number of courses you can complete.

Example 1

Input: courses = [[3,5],[2,4],[4,9],[5,9]]
Output: 3
Explanation: Take the 2-day course (done day 2), the 3-day one (done day 5) and the 4-day one (done day 9). All four would need 14 days.

Example 2

Input: courses = [[1,2]]
Output: 1

Example 3

Input: courses = [[3,2],[4,3]]
Output: 0
Explanation: Neither course fits before its own deadline.

Constraints

  • 1 <= courses.length <= 10^4
  • 1 <= duration, lastDay <= 10^4

Hints for Course Schedule III

  1. Hint 1

    Any set of courses that can be completed can be completed in order of their deadlines.

  2. Hint 2

    Walk the courses by deadline and tentatively take each one, tracking the total time used.

  3. Hint 3

    If the total overshoots the current deadline, drop the longest course taken so far (a max-heap) — that frees the most time for the same count.

How to solve Course Schedule III

Two facts make a greedy work: a feasible set stays feasible when sorted by deadline, and when a new course pushes the total time past its deadline, removing the longest course taken so far keeps the count while leaving the most slack for the future.

Approach

  1. Sort the courses by lastDay.
  2. Keep time (days used) and a max-heap of the durations taken.
  3. For each course: add its duration to time and push it. If time > lastDay, pop the largest duration and subtract it.
  4. Return the heap size.

Why it works

By an exchange argument, among all ways to complete k courses from the first i (in deadline order), the greedy keeps one with the smallest total time — after each step the heap holds the best set of its size. Adding a course either fits (count grows) or does not, in which case dropping the longest duration (possibly the new one) keeps the count and minimises time. Because later deadlines are larger, a smaller total time is never worse for anything that follows.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Sorting by duration instead of deadline fails: a short course with a far deadline should wait.
  • When the overshoot happens, the course to drop may be the one just added — push first, then pop the maximum.
  • A course whose duration exceeds its own lastDay can never be kept; the push-then-pop handles it without a special case.

Reference solution

Python

from typing import List
import heapq

def scheduleCourse(courses: List[List[int]]) -> int:
    heap = []  # negated durations of the courses kept
    time = 0
    for duration, last in sorted(courses, key=lambda c: c[1]):
        time += duration
        heapq.heappush(heap, -duration)
        if time > last:
            time += heapq.heappop(heap)  # drop the longest course so far
    return len(heap)

Java

public static int scheduleCourse(int[][] courses) {
    int[][] cs = courses.clone();
    Arrays.sort(cs, (a, b) -> Integer.compare(a[1], b[1]));
    PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
    int time = 0;
    for (int[] c : cs) {
        time += c[0];
        heap.add(c[0]);
        if (time > c[1]) time -= heap.poll(); // drop the longest course so far
    }
    return heap.size();
}

C++

int scheduleCourse(vector<vector<int>>& courses) {
    vector<vector<int>> cs = courses;
    sort(cs.begin(), cs.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
    priority_queue<int> heap;
    int time = 0;
    for (auto& c : cs) {
        time += c[0];
        heap.push(c[0]);
        if (time > c[1]) {
            time -= heap.top(); // drop the longest course so far
            heap.pop();
        }
    }
    return heap.size();
}

JavaScript

var scheduleCourse = function(courses) {
    var cs = courses.slice().sort(function(a, b) { return a[1] - b[1]; });
    var heap = []; // negated durations of the courses kept
    var time = 0;
    for (var i = 0; i < cs.length; i++) {
        time += cs[i][0];
        heapPush(heap, -cs[i][0]);
        if (time > cs[i][1]) time += heapPop(heap); // drop the longest course so far
    }
    return heap.length;
};

var heapPush = function(h, v) {
    h.push(v);
    var i = h.length - 1;
    while (i > 0) {
        var p = (i - 1) >> 1;
        if (h[p] <= h[i]) break;
        var t = h[p]; h[p] = h[i]; h[i] = t;
        i = p;
    }
};

var heapPop = function(h) {
    var top = h[0];
    var last = h.pop();
    if (h.length > 0) {
        h[0] = last;
        var j = 0;
        for (;;) {
            var l = 2 * j + 1, r = l + 1, s = j;
            if (l < h.length && h[l] < h[s]) s = l;
            if (r < h.length && h[r] < h[s]) s = r;
            if (s === j) break;
            var t = h[s]; h[s] = h[j]; h[j] = t;
            j = s;
        }
    }
    return top;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms