LeetCode 630: Course Schedule III Solution

Master LeetCode problem 630 (Course Schedule III), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

630. Course Schedule III

Hard

Array Greedy Sorting Heap (Priority Queue)

Problem Explanation

Explanation

To solve this problem, we can use a greedy approach. We first sort the courses by their end day. Then, we iterate through the courses and greedily choose the course with the earliest end day that allows us to finish it before the course ends. We keep track of the current total duration and the number of courses taken. If we cannot take the current course, we can try to replace it with a longer duration course we have taken before.

After sorting the courses, we iterate through them and keep track of the total duration taken so far and the maximum number of courses we can take. If adding the current course to the taken duration exceeds the end day of the course, we replace the longest duration course we have taken so far with the current course (if the current course duration is smaller). This way, we always try to maximize the total number of courses taken.

Finally, we return the maximum number of courses taken.

Time complexity: O(n log n) where n is the number of courses Space complexity: O(n) for sorting the courses array

Solution Code

import java.util.Arrays;
import java.util.PriorityQueue;

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 time = 0;
        for (int[] course : courses) {
            if (time + course[0] <= course[1]) {
                time += course[0];
                pq.offer(course[0]);
            } else if (!pq.isEmpty() && pq.peek() > course[0]) {
                time += course[0] - pq.poll();
                pq.offer(course[0]);
            }
        }

        return pq.size();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 630 (Course Schedule III)?

This page provides optimized solutions for LeetCode problem 630 (Course Schedule III) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 630 (Course Schedule III)?

The time complexity for LeetCode 630 (Course Schedule III) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 630 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 630 in Java, C++, or Python.

Back to LeetCode Solutions