算法合集之《浅谈信息学竞赛中的区间问题》

1浅谈信息学竞赛中的区间问题华东师大二附中周小博【摘要】本文对一些常用的区间问题模型做了简单介绍，包括一些算法及其正确性的证明，并从国际、国内的信息学竞赛与大学生程序设计竞赛中选了近10道相关例题，进行简要分析。【关键字】区间模型转化贪心动态规划优化2【引言】在信息学竞赛中，有很多问题最终都能转化为区间问题：例如从若干个区间中选出一些满足一定条件的区间、将各个区间分配到一些资源中、或者将一些区间以某种顺序放置等。这类问题变化繁多，解法各异，需要用到贪心、动态规划等算法，并可以用一些数据结构优化算法。本文将从几个方面对区间问题做一个简单的介绍，给出一些算法及其正确性的证明，具体分如下几个方面进行讨论：1.最大区间调度问题2.多个资源的调度问题3.有最终期限的区间调度问题4.最小区间覆盖问题5.带权区间调度、覆盖问题6.区间和点的有关问题我们将对上述每个问题都给出基本模型、算法、证明及其实现，并从ACM-ICPC、CEOI、CTSC等比赛中选出了近10道相关例题，进行简要分析，有的例题还给出了各种不同的算法及其时间效率的分析。本文中所讨论的问题主要由两个部分组成，一部分为近几年来各类竞赛题的归纳总结，另一部分来自于参考文献。3【正文】1.最大区间调度问题数轴上有n个区间，选出最多的区间，使得这些区间不互相重叠。算法：将所有区间按右端点坐标从小到大排序，顺序处理每个区间。如果它与当前已选的所有区间都没有重叠，则选择该区间，否则不选。证明：显然，该算法最后选出的区间不互相重叠，下面证明所选出区间的数量是最多的。设if为该算法所接受的第i个区间的右端点坐标，ig为某最优解中的第i个区间的右端点坐标。命题1.1当1i时，该算法所接受的第i个区间的右端点坐标if≤某最优解中的第i个区间的右端点坐标ig。该命题可以运用数学归纳法来证明。对于1i，命题显然为真，因为算法第一个选择的区间拥有最小右端点坐标。令1i，假定论断对1i为真，即11iigf。则最优解的第i个可选区间所组成的集合包含于执行该算法时第i个可选区间所组成的集合；而当算法选择第i个区间时，选的是在可选区间中右端点坐标最小的一个，所以有iigf。证毕。设该算法选出了k个区间，而最优解选出了m个区间。命题1.2最优解选出的区间数量m=该算法选出的区间数量k。假设km，根据命题1.1，有kkgf。由于km，必然存在某区间，在kg之后开始，故也在kf之后开始。而该算法一定不会在选了第k个区间后停止，还4会选择更多的区间，产生矛盾。所以km,又因为m是最优解选出区间个数，所以km。综上所述，算法选出的区间是最优解。实现：在判断某个区间与当前已选的所有区间是否重叠时,可以直接判断是否和所选的最后一个区间是否重叠。时间复杂度：排序nnOlog+扫描nO=nnOlog。例题1：LatinAmerica-SouthAmerica2001ProblemA题目大意：基因是由许多外显子（exon）组成，每个外显子都有一个起始位置和一个结束位置。两个外显子能够互相联接必须满足某个外显子的起始位置在另一个外显子的结束位置之后。给出10000nn个外显子，要求找到一条由外显子组成的基因链，使得外显子数量最多。分析：将每个外显子看作一个区间，两端点坐标分别为外显子的起始、结束位置。则现在的问题和原问题基本相同，只是端点上也不能重叠。这里就不写算法了。2.多个资源的调度问题有n个区间和无限多的资源，每个资源上的区间之间不互相重叠。将每个区间都分配到某个资源中，使用到的资源数量最小。定义区间集合深度d为包含任意一点的区间数量的最大值，则显然有：命题2.1需要的资源数至少为d。5设区间1I,2I,…,dI全部包含某一点，则必须把这些区间分配到不同资源中，故至少需要d个资源。其实竞赛中也出现过计算区间集合深度的题目，如NorthAmerica–Northeast2003ProblemE。下面给出计算区间集合深度的算法。d的计算方法：将每个区间拆成两个事件点，按坐标从小到大排序，顺序处理每个区间。记录一个值t，表示当前点被包含次数。每次遇到区间的左端点就+1，遇到右端点就-1。d的值就是在该过程中t的最大值。注意两个相同坐标不同类型的事件点的位置关系和区间是否能在端点处重叠有关，这在排序过程中应该注意。时间复杂度为排序nnOlog+扫描nO=nnOlog由此可得出一个构造算法。算法1：计算出d。将所有区间按左端点坐标从小到大排序，顺序处理每个区间。处理某个区间时，排除在它前面且与之重叠的区间所用到的资源，然后在1,2,3,…,d这些资源中任意分配一个未被排除的资源。证明：设排序后的n个区间分别为1I,2I,…,nI命题2.2每个区间都能分配到一个资源。考虑任何一个区间jI，假设存在t个区间在它前面且与之重叠。一定有dt1，否则由于这1t个区间都包含jI的起始时刻，与d的定义矛盾。故有1dt，从而在d个资源中至少有一个资源没被这t个区间排除。所以对于每个6区间，都至少有一个可分配资源。证毕。命题2.3没有两个互相重叠的区间被分配到了同一个资源。考虑任意两个互相重叠的区间1jI、2jI，其中21jj。当算法在处理区间2jI时，区间1jI所用资源已经被排除，所以不会被分配到同一资源。综上所述，该算法可以成功的构造出正好使用d个资源的一组解，而根据命题2.1，所用资源的下限是d，故该解是用到资源数量最少的解。实现：区间分配资源时，如果直接做排除，则时间复杂度为2nO，当然可以通过记录每个资源的最大右端点坐标以将时间复杂度降为ndO；由于可以每次找一个最大右端点坐标最小的资源，故可以用一个优先队列来储存每个资源的最大右端点坐标。用二叉堆实现该优先队列，每次查找最小值的时间复杂度为1O，修改关键字的时间复杂度为dOlog，分配资源操作的时间复杂度也就降为dnOlog。故总时间复杂度为：d的计算nnOlog+排序nnOlog+分配资源dnOlog=ndnOlog。其实这里可以不计算出d，而通过不断地增加资源数量来使所有区间都能分配到资源。该算法同时也证明了以下命题：命题2.4用到的资源数量的最小值为区间集合深度d。基于这个命题，我们很容易想到另外一种算法。7算法2：计算d。将所有区间按右端点坐标从小到大排序，顺序处理每个区间。对于每个区间，都在1,2,3,…,d这些资源中分配一个可用的且右端点坐标最大的资源。证明：显然每个资源上的区间都不互相重叠，下面证明每个区间都能分配到一个可用资源。用一个元素个数为d的有序表iS（表中元素始终从小到大排序），记录处理i个区间后，各个资源的最大右端点坐标（当某个资源从没被用过时，可认为值为）。同样用表iS表示处理i个区间后，某最优解的状态（根据命题2.5，该表中元素个数也是d）。状态iS不优于iS状态指jSjSdjii,1。命题2.5处理完第1ii个区间后，某最优解此时的状态iS不优于运行该算法后此时的状态iS。该命题可以运用数学归纳法来证明。对于1i，命题显然为真，因为第一个区间无论分配哪个资源，状态都是一样的。令1i，假定论断对1i为真，即jSjSdjii11,1。设处理第i个区间时，该算法分配的资源是11jSi,在最优解中分配的资源为21jSi。设第i个区间的右端点坐标为ie。表iS更新为：iedSjSjSjSSSiiiiii,1,,2,1,1,,2,1111111111；表iS更新为：iedSjSjSjSSSiiiiii,1,,2,1,1,,2,1121212111。而该算法分配的资源11jSi在所有可分配资源中拥用最大右端点坐标，故区间i的左端点坐标小于111jSi，又111111jSjSii，所以12jj。⑴当21jj时：jSjSjSjSiiii11；⑵当12jjj时：jSjSjSjSjSiiiii1111；8⑶当djj1时：jSjSjSjSiiii1111；⑷当dj时：iejSjSii。所以有jSjSdjii,1，证毕。命题2.6每个区间都能分配到一个资源。处理第i个区间时，状态可用1iS表示。最优解肯定能给该区间分配到资源，设为01jSi。根据命题2.5，0101jSjSii。则运行该算法时，至少可以给该区间分配资源01jSi。证毕。综上所述，该算法可以成功的构造出正好使用d个资源的一组解，而根据命题2.1所用资源的下限是d，故该解是用到资源数量最少的解。实现：考虑如何分配资源。如果直接记录每个资源的最大右端点坐标，时间复杂度为ndO。可以用证明中所提到的有序表，用一个平衡二叉树来维护它。每次处理某个区间时，可以在dOlog时间内找到合适资源，并在dOlog时间内修改该资源结束时间。这样做的总时间复杂度也是ndnOlog。第一个构造算法证明了最少所用资源的数量，并用编程复杂度较低的方法构造出了可行解。第二个贪心算法是基于第一个算法的结论得到的，编程复杂度也比第一种高，然而利用它的局部最优性，还可以附加更多的条件。例题2：2004年广东省大学生程序竞赛试题ProblemB题目大意：一个港口被分成了101mm个区域，每个区域最多允许同时停靠910000rr艘船，每艘船都只能停靠在特定的一个区域。有1000001nn艘船，已知每条船的到达时刻、离开时刻和它应该进入的区域。求一个调度方案使得能有最多的船得以停靠。分析：显然每个区域都可以单独处理。可以把船看作一个区间，则该问题是问题2的一个变化：规定使用资源的数量r，问最多能选出多少区间。在算法2上稍加改动即可得出该题的算法。算法：将所有区间按右端点坐标从小到大排序，顺序处理每个区间。对于每个区间，若能找到可用资源，则将该区间安排到一个可用的且右端点坐标最大的资源；若找不到，则不去选它。在前面的证明中我们已经证明了选择资源的局部最优性，唯一剩余的问题是区间的取舍。如果该算法选择了某区间I，而某最优解中没有选它，显然最优解选择了一个与该区间重叠且右端点坐标大于等于它的区间I，我们用I替换I,就构成了一个包含I的最优解；如果该算法没有选择某区间，显然最优解也不会选择该区间。故该算法得出的解就是最优解。实现：还是利用平衡二叉树维护资源信息并寻找合适资源，处理每个区间的时间复杂度是rOlog，故总时间复杂度为：排序nnOlog+处理区间rOnOlog=nrnOlog。3.有最终期限的区间调度问题有n个长度固定、但位置可变的区间，将它们全部放置在),0[上。每个区10间有两个已知参数：长度it和最终期限id，设if为其右端点坐标。定义iiiiiiidfifdfifdfl0，inilL1max。放置所有区间，使它们不互相重叠且最大延迟L最小。算法：将所有区间按最终期限从小到大排序，顺序安排各区间，使中间没有空闲段。证明：由于该算法所有区间都顺序放置，因此区间之间不互相重叠。下面证明该算法求出的L最小。命题3.1存在一个没有空闲段的最优解。若在某最优解中，两相邻区间i、1i之间有空闲段，可将将1i、2i、…、n全部往左移，直至i、1i之间没有空闲段。显然1if、2if、…、nf减小，即1il、2il、…、nl减小。所以此时的最大延迟L一定小于等于原先的L，又L已是最小值，所以LL。因此任何一个有空闲段的最优解不断地进行上述操作后终会变成一个没有空闲时间的最优解。证毕。命题3.2任何一个既没有