Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

630. Course Schedule III

Time: $O(n\log n)$

Space: $O(n)$

			


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();
  }
};




			


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();
  }
}




			


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)