Skip to content

630. Course Schedule III 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 vector<int>& 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();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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)