We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Course Schedule III

Difficulty: Hard

Problem Description

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 Insights

  • Courses must be taken continuously within the limits of their specified last days.
  • The order of courses matters; we need to prioritize shorter courses that allow us to fit more courses within the deadlines.
  • A greedy approach can be applied: always take the courses that finish the earliest, fitting them into the available time.
  • Using a max-heap (priority queue) allows us to efficiently manage the durations of the courses we've decided to take, ensuring we can maximize the number of courses.

Space and Time Complexity

Time Complexity: O(n log n) - primarily due to sorting the courses and managing the max-heap. Space Complexity: O(n) - for storing the courses and the max-heap.

Solution

To solve this problem, we can follow these steps:

  1. Sort the courses based on their last day.
  2. Use a max-heap (priority queue) to keep track of the durations of the courses we select.
  3. Iterate through the sorted list of courses and for each course:
    • If adding this course's duration keeps us within the last day, add it to the heap.
    • If it exceeds the last day, compare it with the longest course in the heap and replace it if the current course is shorter.
  4. The size of the heap at the end will give us the maximum number of courses we can take.

Code Solutions

import heapq

def scheduleCourse(courses):
    # Sort courses based on last day
    courses.sort(key=lambda x: x[1])
    max_heap = []
    total_duration = 0
    
    for duration, last_day in courses:
        # Try to take the course
        if total_duration + duration <= last_day:
            heapq.heappush(max_heap, -duration)  # Push negative to simulate max heap
            total_duration += duration
        elif max_heap and -max_heap[0] > duration:
            # Replace the longest course if the current one is shorter
            total_duration += duration + heapq.heappop(max_heap)  # Remove the longest
            heapq.heappush(max_heap, -duration)  # Add the current one
    
    # The number of courses we can take is the size of the max_heap
    return len(max_heap)
← Back to All Questions