Course Schedule III - Practice Coding Problems

Course Schedule III - Problem

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 1st day and you cannot take two or more courses simultaneously. Return the maximum number of courses that you can take.

Key points:

Each course has a duration and deadline
Courses must be taken sequentially (no overlap)
Goal is to maximize the number of courses completed
You start on day 1

Input & Output

Example 1 — Basic Scheduling

$ Input: courses = [[100,200],[200,300],[1000,2000]]

› Output: 2

💡 Note: We can take courses 1 and 3. Course 1: day 1-100, finishes by day 200. Course 3: day 101-1100, finishes by day 2000. Course 2 would make us exceed its deadline if taken with others.

Example 2 — Single Course

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

› Output: 1

💡 Note: Only one course available. Taking it from day 1-1, finishes by day 2, which meets the deadline.

Example 3 — Tight Deadlines

$ Input: courses = [[3,2],[4,3]]

› Output: 0

💡 Note: No courses can be completed. First course needs 3 days but deadline is day 2. Second course needs 4 days but deadline is day 3.

Constraints

1 ≤ courses.length ≤ 10⁴
1 ≤ duration_i, lastDay_i ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Each course has [duration, deadline] - must finish by deadline

Key Strategy

Sort by deadline, use heap to track and swap courses optimally

Result

Maximum number of courses that can be completed

Key Takeaway

🎯 Key Insight: Sort courses by deadline and use a max heap to optimally swap out the longest course when needed to fit more courses.

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is to sort courses by deadline and use a max heap to track taken courses. When a course can't fit, we replace the longest currently taken course if the new one is shorter. This greedy approach with smart swapping guarantees the optimal solution. Best approach: Greedy with Max Heap. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Sort by Deadline	O(n log n)	O(1)	Sort courses by deadline and greedily take courses that can be completed on time
Brute Force - Try All Combinations	O(2^n × n log n)	O(n)	Generate all possible subsets of courses and find the maximum valid subset
Optimal - Greedy with Max Heap	O(n log n)	O(n)	Sort by deadline, use max heap to track taken courses and swap out longest course when needed

Greedy - Sort by Deadline — Algorithm Steps

Sort courses by deadline (earliest first)
Initialize current day to 0
For each course, check if taking it keeps us within deadline
If yes, take the course and update current day

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort by Deadline

Arrange courses by earliest deadline first

Greedy Selection

Take each course if it fits within deadline

Count Result

Return number of courses taken

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    int* courseA = (int*)a;
    int* courseB = (int*)b;
    return courseA[1] - courseB[1];
}

int solution(int courses[][2], int n) {
    // Sort by deadline
    qsort(courses, n, sizeof(courses[0]), compare);
    
    int currentDay = 0;
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        int duration = courses[i][0];
        int deadline = courses[i][1];
        if (currentDay + duration <= deadline) {
            currentDay += duration;
            count++;
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int courses[1000][2];
    int n = 0;
    
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            courses[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            courses[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            n++;
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(courses, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting courses by deadline takes O(n log n), then single pass takes O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

89.0K Views

Medium-High Frequency

~25 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Sort by Deadline — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler