Last updated on March 2nd, 2025 at 02:44 pm

Here, we see a Course Schedule III LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Greddy

Level of Question

Hard

Course Schedule III LeetCode Solution

1. Problem Statement

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.

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 be ready to take the next course on the 101^st day.
Second, take the 3^rd course, it costs 1000 days so you will finish it on the 1100^th day, and ready to take the next course on the 1101^st day.
Third, take the 2^nd course, it costs 200 days so you will finish it on the 1300^th day.
The 4^th course cannot be taken now, since you will finish it on the 3300^th day, which exceeds the closed date.

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

Example 3:
Input: courses = [[3,2],[4,3]]
Output: 0

2. Coding Pattern Used in Solution

The coding pattern used in this code is “Greedy with Priority Queue (Heap)”. The code uses a priority queue (max-heap) to keep track of the longest course durations and ensures that the total duration does not exceed the course deadlines.

3. Code Implementation in Different Languages

3.1 Course Schedule III C++

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

3.2 Course Schedule III Java

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a,b) -> a[1] - b[1]);
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);
        int total = 0;
        for (int[] course : courses) {
            int dur = course[0], end = course[1];
            if (dur + total <= end) {
                total += dur;
                pq.add(dur);
            } else if (pq.size() > 0 && pq.peek() > dur) {
                total += dur - pq.poll();
                pq.add(dur);
            }
        }
        return pq.size();
    }
}

3.3 Course Schedule III JavaScript

var scheduleCourse = function(courses) {
    courses.sort((a,b) => a[1] - b[1])
    let total = 0, pq = new MaxPriorityQueue({priority: x => x})
    for (let [dur, end] of courses)
        if (dur + total <= end)
            total += dur, pq.enqueue(dur)
        else if (pq.front() && pq.front().element > dur)
            total += dur - pq.dequeue().element, pq.enqueue(dur)
    return pq.size()
};

3.4 Course Schedule III Python

class Solution(object):
    def scheduleCourse(self, courses):
        heap, total = [], 0
        for dur, end in sorted(courses, key=lambda el: el[1]):
            if dur + total <= end:
                total += dur
                heappush(heap, -dur)
            elif heap and -heap[0] > dur:
                total += dur + heappop(heap)
                heappush(heap, -dur)
        return len(heap)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n log n)	O(n)
Java	O(n log n)	O(n)
JavaScript	O(n log n)	O(n)
Python	O(n log n)	O(n)