以区间调度为例
有1,...,n次请求,去获取单个资源,每个请求的开始时间是s(i),结束时间是f(i), 对于请求i和j,如果二者的区间不重合,即f(i)<=s(j) 或者 f(j)<=s(i),那么这两次请求认为是兼容的。比如下面的两个区间是兼容的
而下面存在不兼容的区间
区间调度的问题是,如何才能获取请求的兼容的区间最大的个数呢?
比如上图是3个
可以使用贪心算法。
贪心算法的大致思路是:每次获取问题的一小部分,决定对这小部分数据如何做处理,解决了这部分,再去处理其它的。
关键在于如何选取请求。可以想象有一些方式
可以选择最早结束的请求作为选择的规则,这样能获得最大的兼容区间的个数
选择最早结束的请求作为选择的规则,能获得最大的兼容区间的个数
最优的子集也是最优的
可以举出一个例子,证明使用上述贪心算法的策略不再生效
优先最先完成的贪心算法必定会选择权重为w=1的两个,但是它得到的最终权重是小于w=3的区间。
使用动态规划可以解决。 我不知道该从那个请求开始,那么就去选择所有可能作为第一个请求的地方,然后获取他们的最大值,即得结果。 选取好开始的节点之后,剩下的问题是什么呢?如果选取了第一个请求之后,那么应该排斥掉那些与它不兼容的区间,才能获取兼容区间,那么发生在这个请求之前的请求是否应该考虑?由于选取的规则是认为它是第一个请求,如果有之前的发生,实际上在整个的遍历过程中肯定会经历,所以只需要选取在它之后发生的即可,那么剩下的问题也就是
获取最大的权重的兼容空间也就是考虑,所有子问题中加上当前问题的最大数即可:
时间花销:可以看到一共有O(n)个子问题,因为选取第一个区间之后,其它的所有子问题要做一个max,需要遍历所有的情况,然后记下来,供后续使用。总共的遍历为从1,..,n,所以时间花销为
运行时间可以优化到nlgn;
如果增加条件实在一批机器上运行,要去获取一个最大的兼容区间个数,则是一个NP-hard问题