Skip to content

630. Course Schedule III 👍

  • Time: $O(\texttt{sort})$
  • 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(courses.begin(), courses.end(),
         [](const auto& a, const auto& b) { return a[1] < b[1]; });
    priority_queue<int> maxHeap;

    for (const vector<int>& course : courses) {
      const int duration = course[0];
      const int lastDay = course[1];
      maxHeap.push(duration);
      time += duration;
      // If the current course cannot be taken, check if it can be swapped with
      // a previously taken course that has a 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<>(Collections.reverseOrder());

    for (int[] course : courses) {
      final int duration = course[0];
      final int lastDay = course[1];
      maxHeap.offer(duration);
      time += course;
      // If the current course cannot be taken, check if it can be swapped with
      // a previously taken course that has a 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 the current course cannot be taken, check if it can be swapped with
      # a previously taken course that has a larger duration to increase the
      # time available to take upcoming courses.
      if time > lastDay:
        time += heapq.heappop(maxHeap)

    return len(maxHeap)