这里有 n 门不同的在线课程，他们按从 1 到 n 编号。每一门课程有一定的持续上课时间（课程时间）t 以及关闭时间第 d 天。一门课要持续学习 t 天直到第 d 天时要完成，你将会从第 1 天开始。
给出 n 个在线课程用 (t, d) 对表示。你的任务是找出最多可以修几门课。
示例：
输入: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出: 3
解释:
这里一共有 4 门课程, 但是你最多可以修 3 门:
首先, 修第一门课时, 它要耗费 100 天，你会在第 100 天完成, 在第 101 天准备下门课。
第二, 修第三门课时, 它会耗费 1000 天，所以你将在第 1100 天的时候完成它, 以及在第 1101 天开始准备下门课程。
第三, 修第二门课时, 它会耗时 200 天，所以你将会在第 1300 天时完成它。
第四门课现在不能修，因为你将会在第 3300 天完成它，这已经超出了关闭日期。
提示:
整数 1 <= d, t, n <= 10,000 。
你不能同时修两门课程。
解题思路：
我们首先可以发现，如果两门课 (t1, d1) 和 (t2, d2) 满足 d1 <= d2，即后者的结束时间不晚于前者，那么我们先学习前者再学习后者总是最优的。因为如果先学习前者，即需要满足 x t1 <= d1 且 x t1 t2 <= d2；如果先学习后者，则需要满足 x t2 <= d2 且 x t1 t2 <= d1。如果后者中的 x t1 t2 <= d1 成立，那么显然有 x t1 <= d1 且 x t1 t2 <= d1 <= d2，即前者一定成立；反之如果 x = 0, (t1, d1) = (2, 3), (t2, d2) = (5, 100)，那么前者成立且后者不成立。因此先学习前者再学习后者总是最优的。
基于上面的结论，我们可以将课程按照完成时间 d 递增排序。假设我们在前 i 门课中最多可以选取 k 门课，并且这 k 门课的总时长最短（称为最优方案），那么有下面的不等式：
t1 t2 <= d2
t1 t2 t3 <= d3
...
t1 t2 ... tk <= dk
此时我们需要判断第 i 1 门课 (t0, d0) 是否可选。如果选取的 k 门课的总时长 t 与 t0 之和小于等于 d0，即
t1 t2 ... tk t0 <= d0
那么 (t0, d0) 一定可选，此时前 i 1 门课的最优方案是选取 t1, t2, ..., tk, t0 这 k 1 门课。可以使用反证法来证明，假设可以选取超过 k 1 门课，或者选取 k 1 门课且总时长小于 t1 t2 ... tk t0，那么我们去除 (t0, d0) 这门课，剩余的选取方案一定满足条件，且优于选取 t1, t2, ..., tk 的方案，与之间的假设 t1, t2, ..., tk 是最优方案相矛盾。
如果上述不等式不满足，那么我们找出 t1, t2, ..., tk 中时间最长的那一门课 tj，如果 tj > t0，那么我们可以将 tj 用 t0 代替，即 t1, t2, ..., tj-1, tj 1, ..., tk, t0 是一种最优方案。这里同样可以使用反证法来证明。如果 tj <= t0，那么最优方案仍然为 t1, t2, ..., tk。
因此我们依次遍历每一门课程，通过上面的方法，就可以得到最优方案。我们就可以通过优先队列在若干个数中选出最大值，在遍历每一门课程 (ti, di) 时，依次进行如下操作：
如果当前优先队列中所有课程的时间之和 t 与 ti 之和小于等于 di，那么就把 (ti, di) 加入优先队列中；
如果当前优先队列中所有课程的时间之和 t 与 ti 之和大于 di，那么找到当前优先队列中课程时间最大的课程 (tj, dj)（即为堆顶），如果 tj > ti，则将它移出优先队列，并把 (ti, di) 加入优先队列中。
在所有的课程都判断完毕后，优先队列中包含的课程数目就代表了最多能选择的课程数目。
代码实现
代码语言：javascript复制func scheduleCourse(courses [][]int) int {
sort(courses,0,len(courses)-1)
//fmt.Println(courses)
var index []int
sum:=0
for i:=0;i<len(courses);i {
if sum courses[i][0]<=courses[i][1]{
sum =courses[i][0]
index=priorityQueue(courses,index,i)
}else if len(index)>0 && courses[i][0]<=courses[index[0]][0]{
sum=sum courses[i][0]-courses[index[0]][0]
index=index[1:]
index=priorityQueue(courses,index,i)
}
//fmt.Println(index)
}
return len(index)
}
func priorityQueue(courses [][]int,index []int,i int)[]int{
if len(index)==0{
index=append(index,i)
}else{
ind:=-1
for j:=0;j<len(index);j {
//注意这里是<多个相等，先干掉前面的
if courses[index[j]][0]<courses[i][0]{
ind=j
break;
}
}
if ind==-1{
index=append(index,i)
}else{
//fmt.Println(index[:ind:ind],i,index[ind:],"----",index,ind,courses[i])
index1:=append(index[:ind:ind],i)
index=append(index1,index[ind:]...)
}
}
return index
}
func sort(courses [][]int,start,end int){
p:=start
i:=start
j:=end
tmp:=courses[p]
for i<=j{
for p<=j && courses[j][1]>=tmp[1]{
j--
}
if p<j {
courses[p]=courses[j]
p=j
}
if i<=p && courses[i][1]<=tmp[1]{
i
}
if i<p{
courses[p]=courses[i]
p=i
}
}
courses[p]=tmp
if p>start 1{
sort(courses,start,p-1)
}
if p 1<end{
sort(courses,p 1,end)
}
}
/*
[[5,5],[4,6],[2,6]]
[[7,16],[2,3],[3,12],[3,14],[10,19],[10,16],[6,8],[6,11],[3,13],[6,16]]
[[100,2],[32,50]]
[[100,200],[200,1300],[1000,1250],[2000,3200]]
*/
