630. 课程表 III

题目描述

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

你的学期从第 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 <= 10⁴
1 <= duration_i, lastDay_i <= 10⁴

解法一：优先队列

 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
39


type Priority struct {
    sort.IntSlice
}

func (pq *Priority) Less(i, j int) bool {
    return pq.IntSlice[i] > pq.IntSlice[j]
}

func (pq *Priority) Push(x interface{}) {
    pq.IntSlice = append(pq.IntSlice, x.(int))
}

func (pq *Priority) Pop() interface{} {
    a := pq.IntSlice
    ret := a[len(a)-1]
    pq.IntSlice = a[:len(a)-1]
    return ret
}

func scheduleCourse(courses [][]int) int {
    sort.Slice(courses, func(i, j int) bool {
        return courses[i][1] < courses[j][1]
    })

    pq := &Priority{}
    total := 0
    for _, course := range courses {
        if course[0]+total <= course[1] {
            heap.Push(pq, course[0])
            total += course[0]
        } else if pq.Len() > 0 && pq.IntSlice[0] > course[0] {
            total += course[0] - pq.IntSlice[0]
            pq.IntSlice[0] = course[0]
            heap.Fix(pq, 0)
        }
    }

    return pq.Len()
}