630. Course Schedule III
Explanation
To solve this problem, we can use a greedy approach. We first sort the courses by their end day. Then, we iterate through the courses and greedily choose the course with the earliest end day that allows us to finish it before the course ends. We keep track of the current total duration and the number of courses taken. If we cannot take the current course, we can try to replace it with a longer duration course we have taken before.
After sorting the courses, we iterate through them and keep track of the total duration taken so far and the maximum number of courses we can take. If adding the current course to the taken duration exceeds the end day of the course, we replace the longest duration course we have taken so far with the current course (if the current course duration is smaller). This way, we always try to maximize the total number of courses taken.
Finally, we return the maximum number of courses taken.
Time complexity: O(n log n) where n is the number of courses Space complexity: O(n) for sorting the courses array
import java.util.Arrays;
import java.util.PriorityQueue;
class Solution {
public int scheduleCourse(int[][] courses) {
Arrays.sort(courses, (a, b) -> a[1] - b[1]);
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
int time = 0;
for (int[] course : courses) {
if (time + course[0] <= course[1]) {
time += course[0];
pq.offer(course[0]);
} else if (!pq.isEmpty() && pq.peek() > course[0]) {
time += course[0] - pq.poll();
pq.offer(course[0]);
}
}
return pq.size();
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.