Sponsored
Sponsored
This approach involves using a greedy method combined with a max-heap (or priority queue) to choose which courses to take.
Time Complexity: O(n log n), where n is the number of courses, due to sorting and heap operations.
Space Complexity: O(n), required for the heap storage.
1import heapq
2
3def scheduleCourse(courses):
4 courses.sort(key=lambda x: x[1])
5 max_heap = []
6 total_days = 0
7
8 for duration, last_day in courses:
9 if total_days + duration <= last_day:
10 total_days += duration
11 heapq.heappush(max_heap, -duration)
12 elif max_heap and -max_heap[0] > duration:
13 total_days += duration + heapq.heappop(max_heap)
14 heapq.heappush(max_heap, -duration)
15
16 return len(max_heap)This Python solution sorts the courses based on their last available day. It utilizes a max-heap (by pushing negative durations) to manage the courses being taken such that the longest duration course is easily removable when a constraint breach occurs. The heap size at the end represents the number of courses taken.
This approach defines a DP table where `dp[i][t]` represents the maximum number of courses we can fit into our schedule given the first `i` courses considered and `t` days available. The decision at each step involves either taking or not taking a course. The transition function will decide by taking the maximum between taking the current course (if it fits) or not taking it.
Time Complexity: O(nD), where n is the number of courses and D is the maximum last day.
Space Complexity: O(D) for the DP array.
1import java.util.*;
2
3public class CourseSchedule
This Java solution uses a dynamic programming approach to solve the problem efficiently by iterating backwards through possible days to ensure overlapping updates do not occur, thus propagating maximum course counts correctly at each considered day.