区间调度
?
问题:有一组需求{1,...,n},每个需求i有一个开始结束时间s(i),f(i)对应,如果两个需求没有在时间上重叠,我们就说需求是相容的,求最大的相容子集,即最优子集。
明显的贪心算法啦:
??按照f结束时间升序排序,O(nlogn),
? 依次处理每个需求,假如最优子集集合,顺序删除与之冲突的后续需求,O(n)