《算法合集之《浅谈信息学竞赛中的区间问题》》由会员分享，可在线阅读，更多相关《算法合集之《浅谈信息学竞赛中的区间问题》（45页珍藏版）》请在金锄头文库上搜索。
1、1浅谈信息学竞赛中的区间问题浅谈信息学竞赛中的区间问题华东师大二附中周小博 【摘要摘要】本文对一些常用的区间问题模型做了简单介绍，包括一些算法及其正确性的证明，并从国际、国内的信息学竞赛与大学生程序设计竞赛中选了近 10 道相关例题，进行简要分析。【关键字关键字】区间模型区间模型 转化转化 贪心贪心 动态规划动态规划 优化优化2【引言引言】在信息学竞赛中，有很多问题最终都能转化为区间问题：例如从若干个区间中选出一些满足一定条件的区间、将各个区间分配到一些资源中、或者将一些区间以某种顺序放置等。这类问题变化繁多，解法各异，需要用到贪心、动态规划等算法，并可以用一些数据结构优化算法。本文将从几个方
2、面对区间问题做一个简单的介绍，给出一些算法及其正确性的证明，具体分如下几个方面进行讨论：1.最大区间调度问题2.多个资源的调度问题3.有最终期限的区间调度问题4.最小区间覆盖问题5.带权区间调度、覆盖问题6.区间和点的有关问题我们将对上述每个问题都给出基本模型、算法、证明及其实现，并从 ACM-ICPC、CEOI、CTSC 等比赛中选出了近 10 道相关例题，进行简要分析，有的例题还给出了各种不同的算法及其时间效率的分析。本文中所讨论的问题主要由两个部分组成，一部分为近几年来各类竞赛题的归纳总结，另一部分来自于参考文献。3【正文正文】1.1.最大区间调度问题最大区间调度问题数轴上有个区间，选出
3、最多的区间，使得这些区间不互相重叠。n算法：算法：将所有区间按右端点坐标从小到大排序，顺序处理每个区间。如果它与当前已选的所有区间都没有重叠，则选择该区间，否则不选。证明：证明：显然，该算法最后选出的区间不互相重叠，下面证明所选出区间的数量是最多的。设为该算法所接受的第 个区间的右端点坐标，为某最优解中的ifiig第 个区间的右端点坐标。i命题命题 1.11.1 当当时，该算法所接受的第时，该算法所接受的第 个区间的右端点坐标个区间的右端点坐标某最优解中某最优解中1iiif的第的第 个区间的右端点坐标个区间的右端点坐标。iig该命题可以运用数学归纳法来证明。对于，命题显然为真，因为算法1i第一
4、个选择的区间拥有最小右端点坐标。令，假定论断对为真，即1i1i。则最优解的第 个可选区间所组成的集合包含于执行该算法时第 个11iigfii可选区间所组成的集合；而当算法选择第 个区间时，选的是在可选区间中右端i点坐标最小的一个，所以有。证毕。iigf 设该算法选出了个区间，而最优解选出了个区间。km命题命题 1.21.2 最优解选出的区间数量最优解选出的区间数量= =该算法选出的区间数量该算法选出的区间数量。mk假设，根据命题 1.1，有。由于，必然存在某区间，在km kkgf km 4之后开始，故也在之后开始。而该算法一定不会在选了第个区间后停止，kgkfk还会选择更多的区间，产生矛盾。所
5、以,又因为是最优解选出区间个数，km m所以。km 综上所述，算法选出的区间是最优解。实现：实现：在判断某个区间与当前已选的所有区间是否重叠时,可以直接判断是否和所选的最后一个区间是否重叠。时间复杂度：排序+扫描nnOlog=。 nOnnOlog例题例题 1 1：LatinLatin AmericaAmerica - - SouSout th h AmericaAmerica 20200 01 1 ProblemProblem A A题目大意：题目大意：基因是由许多外显子（exon）组成，每个外显子都有一个起始位置和一个结束位置。两个外显子能够互相联接必须满足某个外显子的起始位置在另一个外显子
6、的结束位置之后。给出个外显子，要求找到一条由外显子10000 nn组成的基因链，使得外显子数量最多。分析：分析：将每个外显子看作一个区间，两端点坐标分别为外显子的起始、结束位置。则现在的问题和原问题基本相同，只是端点上也不能重叠。这里就不写算法了。2.2.多个资源的调度问题多个资源的调度问题有个区间和无限多的资源，每个资源上的区间之间不互相重叠。将每个n区间都分配到某个资源中，使用到的资源数量最小。5定义区间集合深度为包含任意一点的区间数量的最大值，则显然有：d命题命题 2.12.1 需要的资源数至少为需要的资源数至少为。d设区间,全部包含某一点，则必须把这些区间分配到不同资源中，1I2IdI
7、故至少需要个资源。d其实竞赛中也出现过计算区间集合深度的题目，如 North America Northeast 2003 Problem E。下面给出计算区间集合深度的算法。的计算方法：的计算方法：d将每个区间拆成两个事件点，按坐标从小到大排序，顺序处理每个区间。记录一个值 ，表示当前点被包含次数。每次遇到区间的左端点就+1，遇到右端t点就-1。的值就是在该过程中 的最大值。注意两个相同坐标不同类型的事件dt点的位置关系和区间是否能在端点处重叠有关，这在排序过程中应该注意。时间复杂度为排序+扫描=nnOlog nOnnOlog由此可得出一个构造算法。算法算法 1 1：计算出。将所有区间按左端
8、点坐标从小到大排序，顺序处理每个区间。d处理某个区间时，排除在它前面且与之重叠的区间所用到的资源，然后在1,2,3,这些资源中任意分配一个未被排除的资源。d证明：证明：设排序后的个区间分别为,n1I2InI6命题命题 2.22.2 每个区间都能分配到一个资源。每个区间都能分配到一个资源。考虑任何一个区间，假设存在 个区间在它前面且与之重叠。一定有jIt，否则由于这个区间都包含的起始时刻，与的定义矛盾。故有dt11tjId，从而在个资源中至少有一个资源没被这 个区间排除。所以对于每1 dtdt个区间，都至少有一个可分配资源。证毕。命题命题 2.32.3 没有两个互相重叠的区间被分配到了同一个资源
9、。没有两个互相重叠的区间被分配到了同一个资源。考虑任意两个互相重叠的区间、，其中。当算法在处理区间 1jI 2jI21jj 时，区间所用资源已经被排除，所以不会被分配到同一资源。 2jI 1jI综上所述，该算法可以成功的构造出正好使用个资源的一组解，而根据d命题 2.1，所用资源的下限是，故该解是用到资源数量最少的解。d实现：实现：区间分配资源时，如果直接做排除，则时间复杂度为，当然可以通过 2nO记录每个资源的最大右端点坐标以将时间复杂度降为；由于可以每次找 ndO一个最大右端点坐标最小的资源，故可以用一个优先队列来储存每个资源的最大右端点坐标。用二叉堆实现该优先队列，每次查找最小值的时间复
10、杂度为，修改关1O键字的时间复杂度为，分配资源操作的时间复杂度也就降为。dO logdnOlog故总时间复杂度为：的计算+排序+分配资源=dnnOlognnOlogdnOlog。其实这里可以不计算出，而通过不断地增加资源数量来使所有 ndnOlogd区间都能分配到资源。该算法同时也证明了以下命题：7命题命题 2.42.4 用到的资源数量的最小值为区间集合深度用到的资源数量的最小值为区间集合深度。d基于这个命题，我们很容易想到另外一种算法。算法算法 2 2：计算。将所有区间按右端点坐标从小到大排序，顺序处理每个区间。对d于每个区间，都在 1,2,3,这些资源中分配一个可用的且右端点坐标最大d的资
11、源。证明：证明：显然每个资源上的区间都不互相重叠，下面证明每个区间都能分配到一个可用资源。用一个元素个数为的有序表（表中元素始终从小到大排序） ，记diS录处理 个区间后，各个资源的最大右端点坐标（当某个资源从没被用过时，可i认为值为） 。同样用表表示处理 个区间后，某最优解的状态（根据命题iSi2.5，该表中元素个数也是） 。状态不优于状态指。diSiS jSjSdjii,1命题命题 2.52.5 处理完第处理完第个区间后，某最优解此时的状态个区间后，某最优解此时的状态不优于运行该算不优于运行该算1iiiS法后此时的状态法后此时的状态。iS该命题可以运用数学归纳法来证明。对于，命题显然为真，
12、因为第一1i个区间无论分配哪个资源，状态都是一样的。令，假定论断对为真，1i1i即。设处理第 个区间时，该算法分配的资源是, jSjSdjii11,1i 11jSi在最优解中分配的资源为。设第 个区间的右端点坐标为。 21jSiiie表更新为：；iS iedSjSjSjSSSiiiiii,1,2,1,1,2,1111111111表更新为：。iS iedSjSjSjSSSiiiiii,1,2,1,1,2,1121212111而该算法分配的资源在所有可分配资源中拥用最大右端点坐标，故 11jSi8区间 的左端点坐标小于，又，所以。i111jSi111111jSjSii12jj 当时：；21jj j
13、SjSjSjSiiii11当时：；12jjj jSjSjSjSjSiiiii1111当时：；djj1 jSjSjSjSiiii1111当时：。dj iejSjSii所以有，证毕。 jSjSdjii,1命题命题 2.62.6 每个区间都能分配到一个资源。每个区间都能分配到一个资源。处理第 个区间时，状态可用表示。最优解肯定能给该区间分配到资源，i1iS设为。根据命题 2.5，。则运行该算法时，至少可以给 01jSi 0101jSjSii该区间分配资源。证毕。 01jSi综上所述，该算法可以成功的构造出正好使用个资源的一组解，而根据d命题 2.1 所用资源的下限是，故该解是用到资源数量最少的解。d
14、实现：实现：考虑如何分配资源。如果直接记录每个资源的最大右端点坐标，时间复杂度为。可以用证明中所提到的有序表，用一个平衡二叉树来维护它。每 ndO次处理某个区间时，可以在时间内找到合适资源，并在时间内dO logdO log修改该资源结束时间。这样做的总时间复杂度也是。 ndnOlog第一个构造算法证明了最少所用资源的数量，并用编程复杂度较低的方法构造出了可行解。第二个贪心算法是基于第一个算法的结论得到的，编程复杂度也比第一种高，然而利用它的局部最优性，还可以附加更多的条件。9例题例题 2 2：2 2004004 年广东省大学生程序竞赛试年广东省大学生程序竞赛试题题 ProblemProble
15、m B B题目大意：题目大意：一个港口被分成了个区域，每个区域最多允许同时停靠101 mm艘船，每艘船都只能停靠在特定的一个区域。有艘10000rr1000001 nn船，已知每条船的到达时刻、离开时刻和它应该进入的区域。求一个调度方案使得能有最多的船得以停靠。分析：分析：显然每个区域都可以单独处理。可以把船看作一个区间，则该问题是问题2 的一个变化：规定使用资源的数量 ，问最多能选出多少区间。在算法 2 上稍r加改动即可得出该题的算法。算法：算法：将所有区间按右端点坐标从小到大排序，顺序处理每个区间。对于每个区间，若能找到可用资源，则将该区间安排到一个可用的且右端点坐标最大的资源；若找不到，则不去选它。在前面的证明中我们已经证明了选择资源的局部最优性，唯一剩余的问题是区间的取舍。如果该算法选择了某区间，而某最优解中没有选它，显然最I优解选择了一个与该区间重叠且右端点坐标大于等于它的区间，我们用替II换,就构成了一个包含的
