《算法合集之浅谈信息学竞赛中的区间问题》由会员分享，可在线阅读，更多相关《算法合集之浅谈信息学竞赛中的区间问题（44页珍藏版）》请在金锄头文库上搜索。
1、浅谈信息学竞赛中的区间问题华东师大二附中周小博【摘要】本文对一些常用的区间问题模型做了简单介绍，包括一些算法及 其正确性的证明，并从国际、国内的信息学竞赛与大学生程序设计竞 赛中选了近10道相关例题，进行简要分析。【关键字】区间模型转化贪心动态规划优化【引言】在信息学竞赛中，有很多问题最终都能转化为区间问题：例如从 若干个区间中选出一些满足一定条件的区间、将各个区间分配到一些 资源中、或者将一些区间以某种顺序放置等。这类问题变化繁多，解 法各异，需要用到贪心、动态规划等算法，并可以用一些数据结构优 化算法。本文将从几个方面对区间问题做一个简单的介绍，给出一些算法 及其正确性的证明，具体分如下几
2、个方面进行讨论：1最大区间调度问题2. 多个资源的调度问题3. 有最终期限的区间调度问题4. 最小区间覆盖问题5带权区间调度、覆盖问题6区间和点的有关问题我们将对上述每个问题都给出基本模型、算法、证明及其实现， 并从ACM-ICPC、CEOI、CTSC等比赛中选出了近10道相关例题，进行 简要分析，有的例题还给出了各种不同的算法及其时间效率的分析。本文中所讨论的问题主要由两个部分组成，一部分为近几年来各 类竞赛题的归纳总结，另一部分来自于参考文献。【正文】1. 最大区间调度问题数轴上有个区间，选出最多的区间，使得这些区间不互相重叠。算法：将所有区间按右端点坐标从小到大排序，顺序处理每个区间。如
3、果它与当前 已选的所有区间都没有重叠，则选择该区间，否则不选。证明：显然，该算法最后选出的区间不互相重叠，下面证明所选出区间的数量是最 多的。设乞为该算法所接受的第7个区间的右端点坐标，g,为某最优解中的第7个 区间的右端点坐标。命题1.1当时，该算法所接受的第i个区间的右端点坐标/W某最优解中 的第i个区间的右端点坐标&。该命题可以运用数学归纳法来证明。对于2丄1,命题显然为真，因为算法第 一个选择的区间拥有最小右端点坐标。令i 1 ,假定论断对11为真，即人 gi . 则最优解的第i个可选区间所组成的集合包含于执行该算法时第7个可选区间所 组成的集合；而当算法选择第7个区间时，选的是在可选
4、区间中右端点坐标最小 的一个，所以有ft k ,根据命题1. L有fk k ,必然存在某区间，在gk 之后开始，故也在办之后开始。而该算法一定不会在选了第k个区间后停止，还 会选择更多的区间，产生矛盾。所以mk,又因为是最优解选出区间个数， 所以m = ko综上所述，算法选出的区间是最优解。实现：在判断某个区间与当前已选的所有区间是否重叠时，可以直接判断是否和所 选的最后一个区间是否重叠。时间复杂度：排序0(log) +扫描0(n) = o(nlogn)a例题 1： Latin America - Sou th America 2001 Problem A题目大意：基因是由许多外显子(exon
5、)组成，每个外显子都有一个起始位置和一个结 束位置。两个外显子能够互相联接必须满足某个外显子的起始位置在另一个外显 子的结束位置之后。给出(01000)个外显子，要求找到一条由外显子组成 的基因链，使得外显子数量最多。分析：将每个外显子看作一个区间，两端点坐标分别为外显子的起始、结束位置。 则现在的问题和原问题基本相同，只是端点上也不能重叠。这里就不写算法了。2. 多个资源的调度问题有个区间和无限多的资源，每个资源上的区间之间不互相重叠。将每个区 间都分配到某个资源中，使用到的资源数量最小。定义区间集合深度d为包含任意一点的区间数量的最大值，则显然有：命题2.1需要的资源数至少为d。设区间厶，
6、厶，乙全部包含某一点，则必须把这些区间分配到不同资源中， 故至少需要d个资源。其实竞赛中也出现过计算区间集合深度的题目，如North America - Northeast 2003 Problem E。下血给出计算区间集合深度的算法。d的计算方法：将每个区间拆成两个事件点，按坐标从小到大排序，顺序处理每个区间。记 录一个值f,表示当前点被包含次数。每次遇到区间的左端点就+1,遇到右端点 就-1。d的值就是在该过程中f的最大值。注意两个相同坐标不同类型的事件点 的位置关系和区间是否能在端点处重叠有关，这在排序过程中应该注意。时间复 杂度为排序 0（“ log n）+扫描 O（n） = O（ l
7、og n）由此可得出一个构造算法。算法1：计算出d。将所有区间按左端点坐标从小到大排序，顺序处理每个区间。处 理某个区间时，排除在它前面且与之重叠的区间所用到的资源，然后在 1, 2, 3,，d这些资源中任意分配一个未被排除的资源。证明：设排序后的个区间分别为厶，爲，I”命题2. 2每个区间都能分配到一个资源。考虑任何一个区间厶，假设存在/个区间在它前面且与之重叠。一定有 t + ld ,否则由于这/ + 1个区间都包含厶的起始时刻，与d的定义矛盾。故有 td-l,从而在d个资源中至少有一个资源没被这/个区间排除。所以对于每个区间，都至少有一个可分配资源。证毕。命题2. 3没有两个互相重叠的区
8、间被分配到了同一个资源。考虑任意两个互相重叠的区间厶、I”,其中J； j2 O当算法在处理区间乙 时，区间厶所用资源已经被排除，所以不会被分配到同一资源。综上所述，该算法可以成功的构造出正好使用d个资源的一组解，而根据命 题2.1,所用资源的下限是d,故该解是用到资源数量最少的解。实现：区间分配资源时，如果直接做排除，则时间复杂度为0（/）,当然可以通过 记录每个资源的最大右端点坐标以将时间复杂度降为0（“d）；由于可以每次找一 个最大右端点坐标最小的资源，故可以用一个优先队列来储存每个资源的最大右 端点坐标。用二叉堆实现该优先队列，每次查找最小值的时间复杂度为0（1）,修改关键 字的时间复杂
9、度为0（logd）,分配资源操作的时间复杂度也就降为0（nlogd）。故 总时间复杂度为：d的计算O（log） +排序O（log） +分配资源 0（log6/） = 0（logH）o其实这里可以不计算出d,而通过不断地增加资源数量 来使所有区间都能分配到资源。该算法同时也证明了以下命题：命题2. 4用到的资源数量的最小值为区间集合深度d。基于这个命题，我们很容易想到另外一种算法。算法2：计算d。将所有区间按右端点坐标从小到大排序，顺序处理每个区间。对于 每个区间，都在1,2, 3,，d这些资源中分配一个可用的且右端点坐标最大的资 源。证明：显然每个资源上的区间都不互相重叠，下面证明每个区间都能
10、分配到一个可 用资源。用一个元素个数为d的有序表S,（表中元素始终从小到大排序），记录 处理7个区间后，各个资源的最大右端点坐标（当某个资源从没被用过时，可认 为值为-8）。同样用表S；表示处理7个区间后，某最优解的状态（根据命题2. 5, 该表中元素个数也是d）。状态S；不优于S,状态指VIV j6/,S,j1）个区间后，某最优解此时的状态S：不优于运行该算法 后此时的状态S,。该命题可以运用数学归纳法来证明。对于2=1,命题显然为真，因为第一个 区间无论分配哪个资源，状态都是一样的。令il,假定论断对A1为真，即 Vl J。设处理第7个区间时，该算法分配的资源是sz,在 最优解中分配的资源
11、为S也。设第2个区间的右端点坐标为ei。表S,更新为:（S,Jl,Si2,SiU -1,+1,Si久 + 2,S,Jd 1Jej）； 表S：更新为:（S： Jl,S；2,S：2 -11 S：J厶 +1，+ 2,S：Jd -1,ei）。而该算法分配的资源s_z在所有可分配资源中拥用最大右端点坐标，故区 间7的左端点坐标小于s,_d+i,又sz+ivs：Jz+i,所以j2 j； o当 1 厶时：Stj = Sj S：Jj = S；j；当 j2 j 人时:Stj= S;1j Sj+ 1 = S；j；当 心 d 时:Stj = s_i + 1 s：Jj + 1 = S；j；(4)当 j = d 时:S
12、tj = S-j = ei o所以有 Vl jrf,S,jS；j，证毕。命题2. 6每个区间都能分配到一个资源。处理第7个区间时，状态可用S-表示。最优解肯定能给该区间分配到资源， 设为S；_U。根据命题2. 5, SjovS：Jjo。则运行该算法时，至少可以给该 区间分配资源SiUJ。证毕。综上所述，该算法可以成功的构造出正好使用d个资源的一组解，而根据命 题2. 1所用资源的下限是d ,故该解是用到资源数量最少的解。实现：考虑如何分配资源。如果直接记录每个资源的最大右端点坐标，时间复杂度 为0(nd).可以用证明中所提到的有序表，用一个平衡二叉树来维护它。每次处 理某个区间时，可以在0 (
13、logd)时间内找到合适资源，并在O(logd)时间内修改 该资源结束时间。这样做的总时间复杂度也是0(logp)o第一个构造算法证明了最少所用资源的数量，并用编程复杂度较低的方法构 造出了可行解。第二个贪心算法是基于第一个算法的结论得到的，编程复杂度也 比第一种高，然而利用它的局部最优性，还可以附加更多的条件。例题2： 2004年广东省大学生程序竞赛试题Problem B 题目大意：一个港口被分成了 m(l m 10)个区域，每个区域最多允许同时停靠 r（r 10000）艘船，每艘船都只能停靠在特定的一个区域。有zz（l zz 山0 if f, 山“惡曲。放置所有区间，使它们不互相重叠且最大延迟厶最小。算法:将所有区间按最终期限从小到大排序，顺序安排各区间，使中间没有空闲段。证明：由于该算法
