Solution Explanation

This problem asks to find the maximum number of courses that can be taken given constraints on course duration and deadlines. A greedy approach using a priority queue (heap) is efficient for this.

Approach:

1. Sort by Deadline: The courses are first sorted by their deadlines (lastDay). This ensures that we consider courses with earlier deadlines first.

2. Greedy Selection: We iterate through the sorted courses. For each course:

   • We add its duration to the current total time s.
   • We add the course's duration to a max-heap (priority queue). The max-heap keeps track of the durations of the currently enrolled courses. We use a max-heap because we want to quickly identify the longest course to drop if we exceed a deadline.
   • Deadline Check: If the total time s exceeds the current course's deadline, we need to remove a course to make room. We remove the longest course from the max-heap (using heappop or pq.poll()) and subtract its duration from s. This ensures we drop the most time-consuming course first.

3. Result: After processing all courses, the size of the priority queue represents the maximum number of courses that could be completed within their deadlines.

Time Complexity: O(N log N), where N is the number of courses. This is dominated by the sorting step (O(N log N)) and the heap operations (O(N log N) in total, as we perform at most N push and N pop operations).

Space Complexity: O(N) to store the priority queue (heap) in the worst case (if all courses can be taken).

Code Explanation (Python):

import heapq
 
class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda x: x[1]) #Sort by lastDay
        pq = []  # Max-heap to store course durations
        s = 0    # Total time spent on courses
        for duration, last in courses:
            heapq.heappush(pq, -duration) #Negate for max-heap
            s += duration
            while s > last: #Exceeded deadline
                s += heapq.heappop(pq) #Remove longest course
        return len(pq) #Number of courses remaining in the heap

The other language implementations follow the same algorithm, using their respective priority queue implementations (e.g., PriorityQueue in Java, priority_queue in C++). The Go code uses a custom heap implementation for better performance. The TypeScript solution uses a third-party library for the max priority queue. The core logic remains consistent across all languages.