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.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <queue>
5
6using namespace std;
7
8int scheduleCourse(vector<vector<int>>& courses) {
9 sort(courses.begin(), courses.end(), [](const vector<int> &a, const vector<int> &b) {
10 return a[1] < b[1];
11 });
12 priority_queue<int> max_heap;
13 int total_days = 0;
14
15 for (const auto& course : courses) {
16 int duration = course[0], last_day = course[1];
17 if (total_days + duration <= last_day) {
18 total_days += duration;
19 max_heap.push(duration);
20 } else if (!max_heap.empty() && max_heap.top() > duration) {
21 total_days += duration - max_heap.top();
22 max_heap.pop();
23 max_heap.push(duration);
24 }
25 }
26 return max_heap.size();
27}This C++ solution sorts the courses by their last day and uses a max-heap to efficiently track the courses being taken. On exceeding a course's last day constraint, the program replaces the longest course in the current schedule to maximize the number of courses.
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.