#630

Hard

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Course Schedule III

Solve the 'Course Schedule III' problem with a greedy approach involving course selection and validation of constraints.

array greedy sorting heap priority queue

Problem Statement

You are given an array of courses where each course is represented by [duration, lastDay]. The ith course must be taken continuously for the duration specified and must be finished on or before the corresponding last day. Your goal is to determine the maximum number of courses you can complete. You can only take one course at a time, and you start on day 1.

Given the constraints, it is critical to choose courses that allow you to maximize the number of completed courses without violating the lastDay of any course. The key challenge is selecting the optimal subset of courses to take, considering the duration and the time available before their deadlines.

Examples

Example 1

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]

Output: 3

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 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day. Third, take the 2nd course, it costs 200 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 details omitted.

Example 3

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

Output: 0

Example details omitted.

Constraints

1 <= courses.length <= 104
1 <= durationi, lastDayi <= 104

Solution Approach

Greedy Course Selection

Sort the courses by their lastDay. For each course, check if it can be completed by comparing the total time spent on all taken courses and its duration. If adding the course doesn't exceed its lastDay, add it to the schedule.

Priority Queue to Manage Course Durations

Use a max-heap (priority queue) to keep track of the courses you have already taken. This allows you to efficiently discard the longest course if adding a new course would exceed the available time.

Validation of Constraints

Each time a course is considered, ensure that the total time spent up to that point does not exceed the last available day for the course. If it does, remove the course with the longest duration to make room for the new one.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is dominated by the sorting step, which takes O(n log n), where n is the number of courses. The space complexity is O(n) due to the use of a priority queue to manage the courses taken.

What Interviewers Usually Probe

Evaluating the candidate's understanding of greedy algorithms.
Looking for the ability to implement and optimize with a priority queue.
Testing for correct use of sorting and validation in problem solving.

Common Pitfalls or Variants

Common pitfalls

Failing to sort the courses before applying the greedy approach, which may lead to suboptimal course selection.
Not managing the total time correctly when considering course addition.
Mismanaging the priority queue, leading to incorrect course removal or selection.

Follow-up variants

Handling a scenario where courses have the same lastDay, requiring more careful selection based on duration.
Extending the problem to consider courses with variable starting times.
Modifying the problem to allow overlapping courses, testing the algorithm's adaptability.

FAQ

What is the main idea behind the solution for 'Course Schedule III'?

The solution applies a greedy algorithm where we select courses based on their lastDay, using a priority queue to manage the total time spent on courses.

Why do we use a priority queue in this problem?

A priority queue helps manage the courses you've already selected, allowing you to efficiently discard the course with the longest duration if necessary.

How does sorting the courses help solve the problem?

Sorting the courses by their lastDay ensures that we consider the courses in a way that optimizes the number of courses that can be completed before their deadlines.

What is the time complexity of the solution?

The time complexity is O(n log n) due to sorting, with n being the number of courses.

Can this approach handle very large inputs?

Yes, the approach is efficient enough to handle inputs up to the upper constraint limit of 10^4 courses.

terminal

Solution

Solution 1: Greedy + Priority Queue (Max-Heap)

We can sort the courses in ascending order by their end time, and each time select the course with the earliest deadline to take.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda x: x[1])
        pq = []
        s = 0
        for duration, last in courses:
            heappush(pq, -duration)
            s += duration
            while s > last:
                s += heappop(pq)
        return len(pq)

Continue Practicing

#632 smallest range covering elements from k lists #621 task scheduler #502 ipo