Course Schedule III

Hard

Asked by:

15 views

Topics:

Greedy AlgorithmsArrays

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 1^st course, it costs 100 days so you will finish it on the 100^th day, and 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

Constraints:

1 <= courses.length <= 10⁴
1 <= duration_i, lastDay_i <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of courses (length of the input array) and the maximum duration and deadline for a course?
Can the duration or deadline of a course be zero or negative?
If it's impossible to take all the courses, what should I return?
If there are multiple combinations of courses that maximize the number of courses taken, is any one of them acceptable, or is there a specific preference?
Are the courses in the input array already sorted in any way (e.g., by deadline or duration)?

Brute Force Solution

Approach

The brute force way to solve this scheduling problem is to try every possible combination of courses. We want to find the largest number of courses we can take without exceeding any course deadlines. This means exploring all subsets of courses.

Here's how the algorithm would work step-by-step:

Start by considering an empty schedule, taking no courses at all.
Then, consider schedules with only one course.
Next, try schedules with two courses, then three, and so on, up to schedules that include every single course.
For each possible schedule, calculate the total time required to complete all the courses in that schedule by adding up the time needed for each course.
Also, for each schedule, check if we can actually complete all the courses by their deadlines. To do this, we would sort the courses in order of finish date and process courses in that order. If any course's finish date exceeds its deadline, then that schedule is not valid.
Keep track of the largest number of courses found in any valid schedule.
After checking all possible combinations, the largest number of courses in a valid schedule is our answer.

Code Implementation

def course_schedule_brute_force(courses):
    maximum_courses = 0
    number_of_courses = len(courses)

    # Iterate through all possible subsets of courses.
    for i in range(1 << number_of_courses):
        current_schedule = []
        for j in range(number_of_courses):
            if (i >> j) & 1:
                current_schedule.append(courses[j])

        # Sort the courses by their deadlines for evaluation
        current_schedule.sort(key=lambda course: course[1])

        current_time = 0
        can_complete = True

        # Check if the current schedule is valid.
        for course_duration, course_deadline in current_schedule:

            current_time += course_duration

            # If the current schedule is invalid, break
            if current_time > course_deadline:
                can_complete = False
                break

        # Update the maximum number of courses if applicable.
        if can_complete:
            number_of_courses_in_schedule = len(current_schedule)

            #If this schedule is valid, update maximum_courses
            maximum_courses = max(maximum_courses, number_of_courses_in_schedule)

    return maximum_courses

Big(O) Analysis

Time Complexity

O(2^n * n log n) – The algorithm explores all possible subsets of the courses, which leads to 2^n combinations. For each subset, we calculate the total duration and check if the courses can be completed by their deadlines. Sorting the courses in each subset by their finish dates takes O(n log n) time, where n is the number of courses. Since we perform this sorting and validation check for each of the 2^n subsets, the overall time complexity is O(2^n * n log n).

Space Complexity

O(1) – The provided brute force approach implicitly explores subsets of courses, but the plain English explanation does not describe storing all of these subsets explicitly. It only mentions calculating the total time required for a schedule and tracking the largest number of courses found so far. The maximum number of courses, total time, and potentially a few temporary variables for sorting a schedule would use a constant amount of extra space regardless of N, the number of courses. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The problem asks us to take as many courses as possible, given that each course has a duration and a deadline. The key idea is to prioritize courses that finish earlier, but we can also 'swap' courses if a later course is shorter and lets us take more courses overall.

Here's how the algorithm would work step-by-step:

First, sort all the courses by their deadlines, so we consider courses with earlier deadlines first.
Keep track of the courses we're currently taking using a special list. This list represents our current schedule.
Go through each course one by one in the sorted order.
For each course, tentatively add it to our schedule. This means we pretend to take it.
If taking this course makes our total time exceed the deadline of the course we just added, we need to make a change.
To make space, find the longest course we're currently taking and remove it. This 'frees up' time.
By removing the longest course, we're essentially 'swapping' it with the current course if the current course is shorter. This helps us maximize the number of courses we can complete.
After going through all the courses, the number of courses in our current schedule is the maximum number of courses we can take.

Code Implementation

import heapq

def course_schedule_three(courses):
    courses.sort(key=lambda course: course[1])
    
    current_schedule = []
    total_duration = 0

    for duration, last_day in courses:
        total_duration += duration
        heapq.heappush(current_schedule, -duration)

        # If total time exceeds the deadline, remove the longest course.
        if total_duration > last_day:

            total_duration += heapq.heappop(current_schedule)

    # The number of courses in the schedule is the answer.
    return len(current_schedule)

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operations impacting the time complexity are sorting the courses initially, which takes O(n log n) time where n is the number of courses. The algorithm iterates through each course once. Inside the loop, we potentially add elements to a priority queue (heap) and remove the largest element, both of which take O(log n) time. Since we iterate through n courses, and perform O(log n) operations within the loop, the overall complexity becomes O(n log n). Thus, the total runtime is O(n log n) + O(n log n) which simplifies to O(n log n).

Space Complexity

O(N) – The primary space complexity arises from the list used to keep track of the courses we are currently taking, which grows up to a maximum size of N, where N is the total number of courses. In the worst-case scenario, we might tentatively add all courses to this list. While we may remove elements, the list can still potentially hold a number of courses proportional to N. Therefore, the auxiliary space used is O(N).

Edge Cases

Case	How to Handle
Empty courses array	Return 0 immediately as no courses can be taken.
Courses with duration 0	Treat courses with duration 0 like any other course, since they contribute to the course deadline and should be considered if they allow taking more courses.
Courses with deadline 0	These courses can only be taken if there is available time before needing to take any other course.
Large number of courses exceeding memory limits	The priority queue (heap) could potentially grow large; consider using an iterative approach and appropriate data structures to manage memory efficiently.
Courses sorted in decreasing order of deadline	The greedy approach of sorting by deadline still works, ensuring earlier deadlines are prioritized, while the heap handles later deadlines.
Courses with very large durations or deadlines (potential integer overflow)	Use long data types for durations and deadlines to prevent integer overflow during calculations.
No course can be taken within its deadline	The algorithm should correctly return 0 as it won't be able to fit any course into the schedule.
All courses have the same deadline	The algorithm should still correctly determine the maximum number of courses possible considering their durations, filling as much as possible up to that single deadline.

Empty courses array

How to Handle:

Return 0 immediately as no courses can be taken.

Courses with duration 0

How to Handle:

Treat courses with duration 0 like any other course, since they contribute to the course deadline and should be considered if they allow taking more courses.

Courses with deadline 0

How to Handle:

These courses can only be taken if there is available time before needing to take any other course.

Large number of courses exceeding memory limits

How to Handle:

The priority queue (heap) could potentially grow large; consider using an iterative approach and appropriate data structures to manage memory efficiently.

Courses sorted in decreasing order of deadline

How to Handle:

The greedy approach of sorting by deadline still works, ensuring earlier deadlines are prioritized, while the heap handles later deadlines.

Courses with very large durations or deadlines (potential integer overflow)

How to Handle:

Use long data types for durations and deadlines to prevent integer overflow during calculations.

No course can be taken within its deadline

How to Handle:

The algorithm should correctly return 0 as it won't be able to fit any course into the schedule.

All courses have the same deadline

How to Handle:

The algorithm should still correctly determine the maximum number of courses possible considering their durations, filling as much as possible up to that single deadline.