力扣每日一题之课程表Ⅲ

发表于

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

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

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

示例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

方法一：优先队列+贪心

思路

对于两门课\((t1, d1)\)和\((t2, d2)\)，如果后者关闭的时间较晚，即\(d1 \le d2\)，那先学习前者，再学习后者，总是最优的。这是因为：

  • 假设最开始学习的时间点为\(x\)，如果先学习前者，再学习后者，那么需要满足： \[ \begin{cases} x+t_1 \le d_1 \\ x+t_1+t_2\le d_2 \\ \end{cases} \]

  • 如果先学习后者，再学习前者，那么需要满足：

\[ \begin{cases} x+t_2 \le d_2 \\ x+t_1+t_2\le d_1 \\ \end{cases} \]

如果 \(x+t_1+t_2 \le d_1\)成立，由于\(d_1 \le d_2\)，那么\(x+t_1+t_2 \le d_2\)同时成立。这说明，如果能【先学习后者，再学习前者】那么一定能【先学习前者，再学习后者】。如果\(x+t_1+t_2 \le d_2\)成立，则不能推出\(x+t_2+t_1 \le d_1\)成立。虽然能【先学习前者，再学习后者】，但不能【先学习后者，再学习前者】。

因此，我们可以将所有的课程按照关闭时间\(d\)进行升序排序，再依次挑选课程并按照顺序进行学习。

在遍历的过程中，假设我们当前遍历到了第\(i\)门课\((t_i, d_i)\)，而在前\(i-1\)门课程中我们选择了\(k\)门课\((t_{x1}, d_{x1}),(t_{x2}, d_{x2}), ... ,(t_{xk}, d_{xk})\)，满足\(x_1<x_2< \cdots x_k\)，那么有： \[ \begin{cases} t_{x1} \le d_{x1} \\ t_{x1}+t_{x2} \le d_{x2} \\ \cdots \\ t_{x1}+t_{x2}+ \cdots +\le t_{x2} d_{xk}\\ \end{cases} \] 如果上述选择方案是前\(i-1\)门课程的【最优方案】：即不存在能选择\(k+1\)门课程的方法，也不存在能选择\(k\)门课程，且总时长更短的方案，那么我们可以基于该方案与第\(i\)门课程\((t_i, d_i)\)，构造出前\(i\)门课程的最优方案：

这样一来，当我们遍历完所有的\(n\)门课程后，就可以得到最终答案。

算法

我们需要一个数据结构支持【取出\(t\)值最大的那门课程】，因此我们可以使用优先队列。

依次遍历每一门课程，当遍历到\((t_i, d_i)\)时：

  • 如果当前优先队列中所有课程的总时间与\(t_i\)之和小于等于\(d_i\)，那么我们就把\(t_i\)加入优先队列中；
  • 如果当前优先队列中所有课程的总时间与\(t_i\)之和大于\(d_i\)，那么我们找到优先队列的最大元素\(t_{xj}\)。如果\(t_{xj} > t_{i}\)，则将它移出优先队列，并把\(t_i\)加入优先队列中。

在遍历完成之后，优先队列中包含的元素个数即为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func scheduleCourse(courses [][]int) int {
    sort.Slice(courses, func(i, j int) bool {
        return courses[i][1] < courses[j][1]
    })

    h := &Heap{}
    total := 0 // 优先队列中所有课程的总时间
    for _, course := range courses {
        if t := course[0]; total+t <= course[1] {
            total += t
            heap.Push(h, t)
        } else if h.Len() > 0 && t < h.IntSlice[0] {
            total += t - h.IntSlice[0]
            h.IntSlice[0] = t
            heap.Fix(h, 0)
        }
    }
    return h.Len()
}

type Heap struct {
    sort.IntSlice
}

func (h Heap) Less(i, j int) bool {
    return h.IntSlice[i] > h.IntSlice[j]
}

func (h *Heap) Push(x interface{}) {
    h.IntSlice = append(h.IntSlice, x.(int))
}

func (h *Heap) Pop() interface{} {
    a := h.IntSlice
    x := a[len(a)-1]
    h.IntSlice = a[:len(a)-1]
    return x
}