约束条件变更对算法运行时间所带来的影响

以区间调度为例

区间调度

有1,...,n次请求，去获取单个资源,每个请求的开始时间是s(i),结束时间是f(i), 对于请求i和j,如果二者的区间不重合，即f(i)<=s(j) 或者 f(j)<=s(i),那么这两次请求认为是兼容的。比如下面的两个区间是兼容的

而下面存在不兼容的区间

区间调度的问题是，如何才能获取请求的兼容的区间最大的个数呢？

比如上图是3个

如何才能获取请求的兼容的区间最大的个数?

可以使用贪心算法。

贪心算法的大致思路是：每次获取问题的一小部分，决定对这小部分数据如何做处理，解决了这部分，再去处理其它的。

• 使用某种规则去获取一个请求i
• 排除所有与i不兼容的请求
• 重复第一步直到所有请求都处理完毕

关键在于如何选取请求。可以想象有一些方式

1. 按照顺序来，从这种情况看，只能拿到第一个请求，不是最大的，不行

1. 获取时间区间最短的，有如下反例

1. 计算每个请求的不兼容的请求的数量，然后获取最小的不兼容数量的，有如下反例,最少的不兼容的是红色的区间

可以选择最早结束的请求作为选择的规则，这样能获得最大的兼容区间的个数

选择最早结束的请求作为选择的规则，能获得最大的兼容区间的个数

最优的子集也是最优的

加权的区间调度

可以举出一个例子，证明使用上述贪心算法的策略不再生效

优先最先完成的贪心算法必定会选择权重为w=1的两个，但是它得到的最终权重是小于w=3的区间。

使用动态规划可以解决。 我不知道该从那个请求开始，那么就去选择所有可能作为第一个请求的地方，然后获取他们的最大值，即得结果。 选取好开始的节点之后，剩下的问题是什么呢？如果选取了第一个请求之后，那么应该排斥掉那些与它不兼容的区间，才能获取兼容区间，那么发生在这个请求之前的请求是否应该考虑？由于选取的规则是认为它是第一个请求，如果有之前的发生，实际上在整个的遍历过程中肯定会经历，所以只需要选取在它之后发生的即可，那么剩下的问题也就是

获取最大的权重的兼容空间也就是考虑，所有子问题中加上当前问题的最大数即可：

时间花销：可以看到一共有O(n)个子问题，因为选取第一个区间之后，其它的所有子问题要做一个max,需要遍历所有的情况，然后记下来，供后续使用。总共的遍历为从1,..,n，所以时间花销为

运行时间可以优化到nlgn;

如果增加条件实在一批机器上运行，要去获取一个最大的兼容区间个数，则是一个NP-hard问题