跳到主要内容

630.课程表 III

· 阅读需 5 分钟

1、题干​

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

 

示例 1：

输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。

示例 2：

输入：courses = [[1,2]]
输出：1

示例 3：

输入：courses = [[3,2],[4,3]]
输出：0

 

提示:

  • 1 <= courses.length <= 104
  • 1 <= durationi, lastDayi <= 104

2、提交结果​

逻辑和代码比优先队列更简洁，执行效率更高。 1.png

3、解题思路​

破题思路还是看官解。这个题解主要说明如何在保证效率的前提下用更少代码替代优先队列。

每次答优先队列的题都巨难受，因为JS没有优先队列这种数据结构。由于数据范围特征明显1 <= duration[i] <= 1e4，可以用计数排序解这道题，代码比优先队列更简洁。凑巧的是测试用例也比较给力，执行效率比优先队列还好看些。接下来说下如何用计数排序替代优先队列。

设计思路​

优先队列解决的关键问题是快速插入、删除和查找最值。因此我们设计一个名为FPQ的数据结构解决这几个问题，FPQ主要包括的函数和变量是：list、max、constructor()、add()、del()

  • list：元素容器，下标代表待排序的数据，元素值代表下标数字的数量
  • max：所有元素中的最大值；可直接读取，时间复杂度为O(1)O(1)
  • constructor()：构造函数，入参为整数n；时间复杂度为O(n)O(n)；函数逻辑如下：
    • 创建一个大小为n+1的数组list，初始化max为0
  • add()：往list中添加元素，入参为整数n；时间复杂度为O(1)O(1)；函数逻辑如下：
    • list[n]自加1
    • 如果 n > max，则将max赋值为n
  • del()：删除list中的元素，入参为整数 n；最坏时间复杂度为O(n)O(n)；函数逻辑如下：
    • list[n]自减1
    • 如果 n === max 且 list[n]===0，则需要重新计算最大值
    • 计算最大值：从下标 n 开始倒序遍历 list，如果list[n]>0，则将max赋值为list[n]并退出遍历

FPQ的插入方法比优先队列更高效，但删除方法不稳定，其效率可能比优先队列更好也可能更差。另外由于使用计数排序，因此使用场景也很有限。

4、代码​

var scheduleCourse = function (courses) {
  courses.sort((a, b) => a[1] - b[1]);

  const max = courses.reduce((acc, cur) => (cur[0] > acc ? cur[0] : acc), courses[0][0]);
  const pq = new FPQ(max);

  let res = 0;
  let time = 0;
  for (let i = 0; i < courses.length; i++) {
    if (time + courses[i][0] <= courses[i][1]) {
      res++;
      time += courses[i][0];
      pq.add(courses[i][0]);
    } else if (courses[i][0] < pq.max && time + courses[i][0] - pq.max < courses[i][1]) {
      time += courses[i][0] - pq.max;
      pq.add(courses[i][0]);
      pq.del(pq.max);
    }
  }

  return res;
};

class FPQ {
  constructor(n) {
    this.list = new Array(n + 1).fill(0);
    this.max = 0;
  }

  add(n) {
    this.list[n] += 1;
    if (n > this.max) this.max = n;
  }

  del(n) {
    this.list[n] -= 1;
    if (n !== this.max || this.list[n]) return;
    while (n > -1) {
      if (this.list[n] || !n) return (this.max = n);
      n--;
    }
  }
}