## Course Schedule III

• Time:O(n\log n)
• Space:O(n)

## C++

``````class Solution {
public:
int scheduleCourse(vector<vector<int>>& courses) {
int time = 0;
sort(begin(courses), end(courses),
[](const auto& a, const auto& b) { return a[1] < b[1]; });
priority_queue<int> maxHeap;

for (const auto& c : courses) {
const int duration = c[0];
const int lastDay = c[1];
maxHeap.push(duration);
time += c[0];
// if current course could not be taken, check if it's able to swap with a
// previously taken course with larger duration, to increase the time
// available to take upcoming courses
if (time > lastDay)
time -= maxHeap.top(), maxHeap.pop();
}

return maxHeap.size();
}
};
``````

## JAVA

``````class Solution {
public int scheduleCourse(int[][] courses) {
int time = 0;
Arrays.sort(courses, (a, b) -> (a[1] - b[1]));
Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

for (int[] c : courses) {
final int duration = c[0];
final int lastDay = c[1];
maxHeap.offer(duration);
time += c[0];
// if current course could not be taken, check if it's able to swap with a
// previously taken course with larger duration, to increase the time
// available to take upcoming courses
if (time > lastDay)
time -= maxHeap.poll();
}

return maxHeap.size();
}
}
``````

## Python

``````class Solution:
def scheduleCourse(self, courses: List[List[int]]) -> int:
time = 0
maxHeap = []

for duration, lastDay in sorted(courses, key=lambda x: x[1]):
heapq.heappush(maxHeap, -duration)
time += duration
# if current course could not be taken, check if it's able to swap with a
# previously taken course with larger duration, to increase the time
# available to take upcoming courses
if time > lastDay:
time += heapq.heappop(maxHeap)

return len(maxHeap)
``````