golang刷leetcode：课程表 III

这里有 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

解题思路：

对于两门课 (t_1, d_1)和 (t_2, d_2)，如果后者的关闭时间较晚，即 d_1<=d_2，那么我们先学习前者，再学习后者，总是最优的。这是因为：假设开始学习的时间点为 x。如果先学习前者，再学习后者，那么需要满足：

x+t_1<=d_2

x+t_2<=d_2

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

x+t_1<=d_1

x+t_2<=d_1

如果 x+t_1<=d_1,x + t_2 ≤d_1 成立，由于d_1<=d_2 ，那么 x+t_1<=d_2,x + t_2<=d_2 同时成立。这说明如果能「先学习后者，再学习前者」那么一定能「先学习前者，再学习后者」。反之如果 成立，x+t_1<=d_2,x + t_2<=d_2 则不能推出 x+t_1<=d_1,x + t_2 ≤d_1成立，虽然能「先学习前者，再学习后者」，但不能「先学习后者，再学习前者」。

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

在遍历的过程中，假设我们当前遍历到了第 i 门课 (t_i, d_i)，而在前 i-1门课程中我们选择了 k 门课 (t_{x_1}, d_{x_1}), (t_{x_2}, d_{x_2}), ..., (t_{x_k}, d_{x_k})，满足 x_1 < x_2 <... < x_k，那么有：t_{x_1}+...t_{x_k}<=d_{x_k}如果上述选择方案是前 i-1i−1 门课程的「最优方案」：即不存在能选择 k+1 门课程的方法，也不存在能选择 k 门课程，并且总时长更短（小于 t_{x_1} + t_{x_2} +... + t_{x_k}的方案，那么我们可以基于该方案与第 i 门课程 (t_i, d_i)，构造出前 ii 门课程的最优方案：如果 t_{x_1} + t_{x_2} +... + t_{x_k} + t_i <=d_it ，那么我们可以将第 i门课程 (t_i, d_i)直接加入方案，得到选择 k+1门课程的最优方案。这里的「最优性」可以使用反证法来证明。如果存在更优的方案，那么该方案一定包含 (t_i, d_i)，如果不包含，那么说明前 i-1门课程就存在更优的方案，这与我们的假设相矛盾。当最优方案包含 (t_i, d_i)时，根据之前的证明，「先学习前者，再学习后者」总是最优的，我们就可以把 (t_i, d_i) 作为该方案的最后一门课程。由于该方案优于选择 x_1, x_2, ...., x_k的构造方案，因此同时将最后一门课程 i 去除后，该方案仍然优于选择 x_1, x_2, ..., x_kx 的方案，同样说明前 i-1门课程存在更优的方案，这与我们的假设相矛盾。

如果 t_{x_1} + t_{x_2} +... + t_{x_k} + t_i > d_it ，那么我们无法将第 i 门课程 (t_i, d_i)直接加入方案。我们可以使用类似的反证法，证明出此时前 i 门课程不可能存在选择 k+1 门课程的更优方案，因此我们的目标仍然为选择 k 门课程，但最小化它们的总时间，为后续的课程腾出更多的时间。如果 t_{x_1}, t_{x_2}, ..., t_{x_k}都小于等于 t_i，那么我们显然没有办法通过第 i 门课来使得总时间更小。但如果其中时间最长的那门课（记为 t_{x_j}满足 t_{x_j} > t_i，那么我们就可以尝试将第 x_j 门课程替换成第 i门课程了。这样的替换会使得总时间减少 t_{x_j} - t_i ，也是我们能做到的减少的上限了。那么将第 x_j 门课程替换成第 i 门课程后，这些课程是否满足题目的要求呢？我们将这些课程按照 x_1, x_2,..., x_{j-1}, x_{j+1},...., x_k, ix的顺序进行学习：对于 x_1, x_2,..., x_{j-1} ，它们需要满足的不等式与之前是一致的，因此仍然满足要求；对于 x_{j+1}, ..., x_{k} ，原先需要满足的不等式的左侧少了 t_{x_j} 这一项，由于是左侧 ≤ 右侧，因此仍然满足要求；对于 i，由于 t_{x_1} + t_{x_2} +...+ t_{x_k}<= d_{x_k}成立，而 t_{x_{j}} > t_i ，因此：t_{x_1} + t_{x_2} +...+ t_{x_{j-1}} + t_{x_{j+1}} +... + t_{x_k} + t_i<= d_{x_k}满足要求。

这就说明我们可以将第 x_j门课程替换成第 i 门课程。这样一来，当我们遍历完所有的 n 门课程后，就可以得到最终的答案。

算法

我们需要一个数据结构支持「取出 tt 值最大的那门课程」，因此我们可以使用优先队列（大根堆）。

我们依次遍历每一门课程，当遍历到 (t_i, d_i) 时：如果当前优先队列中所有课程的总时间与 t_i之和小于等于 d_i，那么我们就把 t_i加入优先队列中；如果当前优先队列中所有课程的总时间与 t_i之和大于 d_i ，那么我们找到优先队列中的最大元素 t_{x_j}。如果 t_{x_j} > t_i ，则将它移出优先队列，并把 t_i加入优先队列中。在遍历完成后，优先队列中包含的元素个数即为答案。

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
}