Leetcode

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)