630.课程表III

链接：630.课程表III
难度：Hard
标签：贪心、数组、排序、堆（优先队列）
简介：返回你最多可以修读的课程数目。

题解 1 - typescript

• 编辑时间：2021-12-14
• 执行用时：180ms
• 内存消耗：47.4MB
• 编程语言：typescript
• 解法介绍：按照结束时间排序后，每次取出值存入大根堆，维护当前需要的总时间 sum，当 sum 大于结束时间时，移除堆顶。

class Heap<T = number> {
  private arr: T[] = [];
  get isEmpty() {
    return this.size === 0;
  }
  get size() {
    return this.arr.length;
  }
  get top() {
    return this.arr[0];
  }
  constructor(private compare: (t1: T, t2: T) => number) {}
  add(num: T): void {
    this.arr.push(num);
    this.shiftUp(this.size - 1);
  }
  remove(): T {
    const num = this.arr.shift()!;
    if (this.size) {
      this.arr.unshift(this.arr.pop()!);
      this.shiftDown(0);
    }
    return num;
  }
  private shiftUp(index: number): void {
    if (index === 0) return;
    const parentIndex = (index - 1) >> 1;
    if (this.compare(this.arr[index], this.arr[parentIndex]) > 0) {
      [this.arr[index], this.arr[parentIndex]] = [this.arr[parentIndex], this.arr[index]];
      this.shiftUp(parentIndex);
    }
  }
  private shiftDown(index: number): void {
    let childrenIndex = index * 2 + 1;
    if (childrenIndex > this.size - 1) return;
    if (
      childrenIndex + 1 <= this.size - 1 &&
      this.compare(this.arr[childrenIndex + 1], this.arr[childrenIndex]) > 0
    ) {
      childrenIndex++;
    }
    if (this.compare(this.arr[childrenIndex], this.arr[index]) > 0) {
      [this.arr[childrenIndex], this.arr[index]] = [this.arr[index], this.arr[childrenIndex]];
      this.shiftDown(childrenIndex);
    }
  }
  *[Symbol.iterator](): IterableIterator<T> {
    for (const t of this.arr) {
      yield t;
    }
  }
}
function scheduleCourse(courses: number[][]): number {
  const heap = new Heap<number>((a, b) => a - b);
  let sum = 0;
  for (const [dur, last] of courses.sort((a, b) => a[1] - b[1])) {
    sum += dur;
    heap.add(dur);
    if (sum > last) sum -= heap.remove();
  }
  return heap.size;
}

题解 2 - cpp

• 编辑时间：2023-09-11
• 执行用时：256ms
• 内存消耗：53.61MB
• 编程语言：cpp
• 解法介绍：拓扑排序。

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        int sum = 0;
        priority_queue<int> q;
        sort(courses.begin(), courses.end(), [&](auto &a, auto &b) {
            return a[1] < b[1];
        });
        for (auto &course : courses) {
            sum += course[0];
            q.push(course[0]);
            if (sum > course[1]) {
                sum -= q.top();
                q.pop();
            }
        }
        return q.size();
    }
};

题解 3 - python

• 编辑时间：2023-09-11
• 执行用时：124ms
• 内存消耗：19.54MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda o: o[1])
        q = []
        sum = 0
        for [d, e] in courses:
            sum += d
            heappush(q, -d)
            if sum > e:
                sum -= -heappop(q)
        return len(q)

题解 4 - rust

• 编辑时间：2023-09-11
• 执行用时：32ms
• 内存消耗：29.7MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn schedule_course(mut courses: Vec<Vec<i32>>) -> i32 {
        courses.sort_by_key(|o| o[1]);
        let mut sum = 0;
        let mut q = std::collections::BinaryHeap::<i32>::new();
        for course in courses {
            sum += course[0];
            q.push(course[0]);
            if sum > course[1] {
                sum -= q.pop().unwrap();
            }
        }
        q.len() as i32
    }
}