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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Course Schedule III

Number: 630

Difficulty: Hard

Paid? No

Companies: Amazon, Flipkart, Works Applications

Problem Description

Given an array of courses where each course is represented as [duration, lastDay], determine the maximum number of courses that can be taken. Courses must be taken continuously, starting from day 1, and each course must be completed by its lastDay without any overlap.

Key Insights

  • Sort courses based on their lastDay to prioritize courses with earlier deadlines.
  • Use a max-heap to keep track of the durations of the selected courses.
  • Maintain a running total of the time required for all selected courses.
  • If the total time exceeds the current course's deadline, remove the course with the longest duration from the schedule.
  • This greedy approach ensures you select the maximum number of courses possible.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting and heap operations. Space Complexity: O(n) for the heap and additional storage for the sorted list.

Solution

The solution begins by sorting the courses by their lastDay. Then, as we iterate through each course, the course duration is added to a running total and pushed onto a max-heap (implemented using negative values in Python or a custom comparator in other languages). If at any point the running total exceeds the current course's deadline, the longest duration course (the root of the max-heap) is removed, reducing the total time and potentially allowing more courses to fit within their deadlines. This greedy strategy ensures the schedule contains the optimal number of courses.

Code Solutions

import heapq

def scheduleCourse(courses):
    # Sort the courses by their lastDay (deadline)
    courses.sort(key=lambda c: c[1])
    total_time = 0
    max_heap = []  # Using negative values to simulate a max-heap

    for duration, deadline in courses:
        total_time += duration
        # Push negative duration to simulate max heap behavior
        heapq.heappush(max_heap, -duration)
        
        # If the total time exceeds the deadline, remove the course with the longest duration
        if total_time > deadline:
            longest_duration = -heapq.heappop(max_heap)
            total_time -= longest_duration
            
    return len(max_heap)

# Example usage:
courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
print(scheduleCourse(courses))  # Expected Output: 3
← Back to All Questions