浅谈信息学竞赛中的区间问题.doc

浅谈信息学竞赛中的区间问题华东师大二附中周小博【摘要】本文对一些常用的区间问题模型做了简单介绍，包括一些算法及其正确性的证明，并从国际、国内的信息学竞赛与大学生程序设计竞赛中选了近10道相关例题，进行简要分析。【关键字】区间模型 转化 贪心 动态规划 优化【引言】在信息学竞赛中，有很多问题最终都能转化为区间问题：例如从若干个区间中选出一些满足一定条件的区间、将各个区间分配到一些资源中、或者将一些区间以某种顺序放置等。这类问题变化繁多，解法各异，需要用到贪心、动态规划等算法，并可以用一些数据结构优化算法。本文将从几个方面对区间问题做一个简单的介绍，给出一些算法及其正确性的证明，具体分如下几个方面进行讨论：1.最大区间调度问题2.多个资源的调度问题3.有最终期限的区间调度问题4.最小区间覆盖问题5.带权区间调度、覆盖问题6.区间和点的有关问题我们将对上述每个问题都给出基本模型、算法、证明及其实现，并从ACM-ICPC、CEOI、CTSC等比赛中选出了近10道相关例题，进行简要分析，有的例题还给出了各种不同的算法及其时间效率的分析。本文中所讨论的问题主要由两个部分组成，一部分为近几年来各类竞赛题的归纳总结，另一部分来自于参考文献。【正文】1.最大区间调度问题数轴上有个区间，选出最多的区间，使得这些区间不互相重叠。算法：将所有区间按右端点坐标从小到大排序，顺序处理每个区间。如果它与当前已选的所有区间都没有重叠，则选择该区间，否则不选。证明：显然，该算法最后选出的区间不互相重叠，下面证明所选出区间的数量是最多的。设为该算法所接受的第个区间的右端点坐标，为某最优解中的第个区间的右端点坐标。命题1.1 当时，该算法所接受的第个区间的右端点坐标某最优解中的第个区间的右端点坐标。该命题可以运用数学归纳法来证明。对于，命题显然为真，因为算法第一个选择的区间拥有最小右端点坐标。令，假定论断对为真，即。则最优解的第个可选区间所组成的集合包含于（前者属于后者）执行该算法时第个可选区间所组成的集合；而当算法选择第个区间时，选的是在可选区间中右端点坐标最小的一个，所以有。证毕。（理解）设该算法选出了个区间，而最优解选出了个区间。命题1.2 最优解选出的区间数量=该算法选出的区间数量。假设，根据命题1.1，有。由于，必然存在某区间，在之后开始，故也在之后开始。而该算法一定不会在选了第个区间后停止，还会选择更多的区间，产生矛盾。所以,又因为是最优解选出区间个数，所以。综上所述，算法选出的区间是最优解。实现：在判断某个区间与当前已选的所有区间是否重叠时,可以直接判断是否和所选的最后一个区间是否重叠。时间复杂度：排序+扫描=。例题1：Latin America - South America 2001 Problem A题目大意：基因是由许多外显子（exon）组成，每个外显子都有一个起始位置和一个结束位置。两个外显子能够互相联接必须满足某个外显子的起始位置在另一个外显子的结束位置之后。给出个外显子，要求找到一条由外显子组成的基因链，使得外显子数量最多。分析：将每个外显子看作一个区间，两端点坐标分别为外显子的起始、结束位置。则现在的问题和原问题基本相同，只是端点上也不能重叠。这里就不写算法了。2.多个资源的调度问题有个区间和无限多的资源，每个资源上的区间之间不互相重叠。将每个区间都分配到某个资源中，使用到的资源数量最小。定义区间集合深度为包含任意一点的区间数量的最大值，则显然有：命题2.1 需要的资源数至少为。设区间,全部包含某一点，则必须把这些区间分配到不同资源中，故至少需要个资源。其实竞赛中也出现过计算区间集合深度的题目，如North America Northeast 2003 Problem E。下面给出计算区间集合深度的算法。的计算方法：将每个区间拆成两个事件点，按坐标从小到大排序，顺序处理每个区间。记录一个值，表示当前点被包含次数。每次遇到区间的左端点就+1，遇到右端点就-1。的值就是在该过程中的最大值。注意两个相同坐标不同类型的事件点的位置关系和区间是否能在端点处重叠有关，这在排序过程中应该注意。时间复杂度为排序+扫描=由此可得出一个构造算法。算法1：计算出。将所有区间按左端点坐标从小到大排序，顺序处理每个区间。处理某个区间时，排除在它前面且与之重叠的区间所用到的资源，然后在1,2,3,这些资源中任意分配一个未被排除的资源。证明：设排序后的个区间分别为,命题2.2 每个区间都能分配到一个资源。考虑任何一个区间，假设存在个区间在它前面且与之重叠。一定有，否则由于这个区间都包含的起始时刻，与的定义矛盾。故有，从而在个资源中至少有一个资源没被这个区间排除。所以对于每个区间，都至少有一个可分配资源。证毕。命题2.3 没有两个互相重叠的区间被分配到了同一个资源。考虑任意两个互相重叠的区间、，其中。当算法在处理区间时，区间所用资源已经被排除，所以不会被分配到同一资源。综上所述，该算法可以成功的构造出正好使用个资源的一组解，而根据命题2.1，所用资源的下限是，故该解是用到资源数量最少的解。实现：区间分配资源时，如果直接做排除，则时间复杂度为，当然可以通过记录每个资源的最大右端点坐标以将时间复杂度降为；由于可以每次找一个最大右端点坐标最小的资源，故可以用一个优先队列来储存每个资源的最大右端点坐标。用二叉堆实现该优先队列，每次查找最小值的时间复杂度为，修改关键字的时间复杂度为，分配资源操作的时间复杂度也就降为。故总时间复杂度为：的计算+排序+分配资源=。其实这里可以不计算出，而通过不断地增加资源数量来使所有区间都能分配到资源。该算法同时也证明了以下命题：命题2.4 用到的资源数量的最小值为区间集合深度。基于这个命题，我们很容易想到另外一种算法。算法2：计算。将所有区间按右端点坐标从小到大排序，顺序处理每个区间。对于每个区间，都在1,2,3,这些资源中分配一个可用的且右端点坐标最大的资源。证明：显然每个资源上的区间都不互相重叠，下面证明每个区间都能分配到一个可用资源。用一个元素个数为的有序表（表中元素始终从小到大排序），记录处理个区间后，各个资源的最大右端点坐标（当某个资源从没被用过时，可认为值为）。同样用表表示处理个区间后，某最优解的状态（根据命题2.5，该表中元素个数也是）。状态不优于状态指。命题2.5 处理完第个区间后，某最优解此时的状态不优于运行该算法后此时的状态。该命题可以运用数学归纳法来证明。对于，命题显然为真，因为第一个区间无论分配哪个资源，状态都是一样的。令，假定论断对为真，即。设处理第个区间时，该算法分配的资源是,在最优解中分配的资源为。设第个区间的右端点坐标为。表更新为：；表更新为：。而该算法分配的资源在所有可分配资源中拥用最大右端点坐标，故区间的左端点坐标小于，又，所以。当时：；当时：；当时：；当时：。所以有，证毕。命题2.6 每个区间都能分配到一个资源。处理第个区间时，状态可用表示。最优解肯定能给该区间分配到资源，设为。根据命题2.5，。则运行该算法时，至少可以给该区间分配资源。证毕。综上所述，该算法可以成功的构造出正好使用个资源的一组解，而根据命题2.1所用资源的下限是，故该解是用到资源数量最少的解。实现：考虑如何分配资源。如果直接记录每个资源的最大右端点坐标，时间复杂度为。可以用证明中所提到的有序表，用一个平衡二叉树来维护它。每次处理某个区间时，可以在时间内找到合适资源，并在时间内修改该资源结束时间。这样做的总时间复杂度也是。第一个构造算法证明了最少所用资源的数量，并用编程复杂度较低的方法构造出了可行解。第二个贪心算法是基于第一个算法的结论得到的，编程复杂度也比第一种高，然而利用它的局部最优性，还可以附加更多的条件。例题2：2004年广东省大学生程序竞赛试题 Problem B题目大意：一个港口被分成了个区域，每个区域最多允许同时停靠艘船，每艘船都只能停靠在特定的一个区域。有艘船，已知每条船的到达时刻、离开时刻和它应该进入的区域。求一个调度方案使得能有最多的船得以停靠。分析：显然每个区域都可以单独处理。可以把船看作一个区间，则该问题是问题2的一个变化：规定使用资源的数量，问最多能选出多少区间。在算法2上稍加改动即可得出该题的算法。算法：将所有区间按右端点坐标从小到大排序，顺序处理每个区间。对于每个区间，若能找到可用资源，则将该区间安排到一个可用的且右端点坐标最大的资源；若找不到，则不去选它。在前面的证明中我们已经证明了选择资源的局部最优性，唯一剩余的问题是区间的取舍。如果该算法选择了某区间，而某最优解中没有选它，显然最优解选择了一个与该区间重叠且右端点坐标大于等于它的区间，我们用替换,就构成了一个包含的最优解；如果该算法没有选择某区间，显然最优解也不会选择该区间。故该算法得出的解就是最优解。实现：还是利用平衡二叉树维护资源信息并寻找合适资源，处理每个区间的时间复杂度是，故总时间复杂度为：排序+处理区间=。3.有最终期限的区间调度问题有个长度固定、但位置可变的区间，将它们全部放置在上。每个区间有两个已知参数：长度和最终期限，设为其右端点坐标。定义，。放置所有区间，使它们不互相重叠且最大延迟最小。算法：将所有区间按最终期限从小到大排序，顺序安排各区间，使中间没有空闲段。证明：由于该算法所有区间都顺序放置，因此区间之间不互相重叠。下面证明该算法求出的最小。命题3.1 存在一个没有空闲段的最优解。若在某最优解中，两相邻区间、之间有空闲段，可将将、全部往左移，直至、之间没有空闲段。显然、减小，即、减小。所以此时的最大延迟一定小于等于原先的，又已是最小值，所以。因此任何一个有空闲段的最优解不断地进行上述操作后终会变成一个没有空闲时间的最优解。证毕。命题3.2 任何一个既没有逆序、又没有空闲段的解有着相同的最大延迟。如果解中既没有逆序、又没有空闲段，那么相同最终期限的区间只有在次序上可能不同。而这些区间的最大延迟只和最后一个区间的右端点坐标有关，区间的次序却并不影响最后一个区间的右端点坐标，所以最大延迟始终相同。证毕。命题3.3 既没有逆序、又没有空闲段的解是最优解。根据命题3.1，存在一个没有空闲段的最优解。假设某最优解中相邻的某两区间、为逆序关系，即有。设区间的左端点坐标为，若交换两区间，则原来两区间的右端点坐标为，现在则分别为，。设两区间在交换前后的延迟分别为、。因为，所以、不优于、。因此一个存在逆序的解交换相邻的逆序项可以使之更优，只要将一个有逆序的解不断进行上述操作后都能成为一个无逆序的解。证毕。综上所述，该算法成功构造了一个最优解。实现：按算法直接模拟。时间复杂度：排序+扫描=。一般在区间位置可变时，最优解中各区间位置常常是按照最终期限排序，交换最终期限互为逆序的区间总能使结果更优。当然区间带权时，要另外考虑。例题3.1：CTSC 2007 DAY2 pendant题目大意：有粒缀珠，每粒缀珠有两个参数：挂钩的最大承受重量和本身重量。将缀珠经挂钩连接后挂起形成挂坠，要求每粒缀珠下方的缀珠重量之和不能超过它挂钩的最大承受重量。问挂坠最多能由多少个缀珠组成，并求出满足缀珠数量最多时挂坠质量的最小值。分析：把每粒缀珠看作一个长度为的区间，这些区间的位置是可变的。则问题转化为：选出最多的区间，并将它们不互相重叠地放置在上，使得左端点坐标不能超过。在保证区间数量最大时，需求出最大右端点坐标的最小值。根据原问题，容易证明下面这个结论：显然必有一个最有解，它的区间按最后期限排序，连续地放置在上。（证明和原问题的证明方法类似）在这个结论的基础上，可以得出以下两种算法。算法1：容易想到一个的动态规划。将区间按的值从小到大排序，设为前个区间，选取了个区间后，最大右端点坐标的最小值。则对于任意一个合法的，做下面的两个动态转移：若第个区间不选：；若，则可以选择该区间：。状态数为，状态转移时间为，故时间复杂度为。然而仅仅是不够的，还需要优化。优化：设,显然不变时，随着的增大而呈单调递增（如果,那么肯定不是最大右端点坐标的最小值）。故每次从递推时，可以进行如下的两个操作：找到两个位置，；删除，将,的值向后平移到, ，并将的值修改为。时间复杂度：用一棵平衡二叉树维护，则从递推的时间复杂度为，所以总时间复杂度为：排序+的维护=。该算法要用到平衡二叉树，编程复杂度较大。其实仔细分析算法1，并加以改进，就可以得到一个贪心的算法。算法2：维护一个按排序的有序表，初始为空。将所有区间按长度从小到大排序，依次处理。处理某个区间时，若它能够放入有序表，则选择该区间并放入表中，否则不选择。最后的表即是要求的状态。实现：算法的瓶颈在有序表的维护上。如果直接模拟该表的所有操作，时间复杂度是。用线段树来维护该表，可以在的时间里完成每个区间的取舍及插入操作（这些操作并不是非常容易实现，但与论文主题无关，这里不再细写）。因此，总时间复杂度为。例题3.2：Europe - Southeastern 2007 Problem D题目大意：一家银行收到了个贷款申请，每个贷款都最晚要在时完成，利润为。每个贷款需要一个单位时间处理，银行在同一时间内最多可以接受个贷款。求如何安排才能获得最大利润。分析：将每个贷款申请看作一个单位长度、位置可变且带权的区间，则题目转化为选出一些区间，将它们不互相重叠地放在个资源上，使利润最大，且区间的左端点不得超过。可以用与例题3.1算法2类似的贪心算法解决该问题。算法：将这些区间按照权值从大到小排序，顺序处理每个区间。设。由于区间都是单位长度的，我们可以用一维数组来记录当前的情况，表示被覆盖次数，根据题意有。处理第个区间时，若可以选择该区间（即），则将该区间放置到一个最大的一个位置，即，否则就不选择该区间。处理每个区间时，若直接模拟，时间复杂度是，最好还是做适当优化。优化1：若用一棵线段树来维护数组，可以在的时间里处理每个区间。总时间复杂度为：排序+处理每个区间=。优化2：每次的值增加后，若，则将之所属集合与前面的所属集合合并成一个新集合。处理第个区间时，它选择的位置必是所在集合中的最前面的元素，（若最前面的元素是且，则表示该区间不能被选择）。如果我们用并查集来实现集合的各种操作，维护它的时间复杂度可近似地看作。总时间复杂度：排序+处理每个区间=。第1种优化由于用到了线段树，不论在空间上还是在时间上都有着巨大的系数；而第2种优化用到的空间非常小，且在时间效率和编程复杂度两方面都比第1种好很多。4.最小区间覆盖问题有个区间，选择尽量少的区间，使得这些区间完全覆盖某线段。算法：将所有区间按左端点坐标从小到大排序，顺序处理每个区间。每次选择覆盖点的区间中右端点坐标最大的一个，并将更新为该区间的右端点坐标，直到选择的区间已包含。证明：显然，该算法最后选出来的区间完全覆盖，下面证明所选出区间的数量是最少的。设为该算法所接受的第个区间的右端点坐标，为某最优解中第个区间的右端点坐标。命题4.1 当时：该算法所接受的第个区间的右端点坐标某最优解中的第个区间的右端点坐标。该命题可以运用数学归纳法来证明。对于，命题显然为真，因为算法第一个选择的区间是能覆盖点的区间中右端点坐标最大的那个。令，假定论断对为真，即，最优解中选的第个区间的右端点坐标为,设它的左端点坐标为。由于该区间覆盖，即。当时，由于，有；当时，有，此时最优解所选择的区间覆盖点,又算法选择的第个区间是右端点坐标最大的那个，故。证毕。设该算法选出了个区间，而最优解选出了个区间。命题4.2 最优解选出的区间数量=该算法选出的区间数量。假设，根据命题4.1，有。根据该算法，因此该最优解不可能覆盖，产生矛盾。所以,又因为是最优解中选出区间个数，所以。综上所述，算法选出的区间是最优解。实现：选择区间可以通过线性扫描来实现。时间复杂度：排序+扫描=。例题4：ACM/ICPC Regional Warm-up Contest 2002 Problem E题目大意：有一块草坪，长为，宽为，在它的中心线的位置处装有个点状的喷水装置。每个喷水装置喷水的效果是以它为中心半径为的圆都被润湿。请选择尽量少的喷水装置，把整个草坪全部润湿。如图所示：分析：显然覆盖整个草坪的充要条件是要能覆盖上边界。将每个喷水设置能覆盖的一段上边界看成一个区间，转化后的问题就是原问题。5.带权区间调度、覆盖问题若区间带权，如何解决调度、覆盖一类问题呢？这时，刚才一直用的贪心算法已经不再普遍适用，大部分情况下，只能用更一般性的方法动态规划。例题5.1：Europe - Northeastern Europe 2004 Problem J题目大意：有只可爱的小海龟在赛跑。询问每只小海龟它是第几名，它会回答你两个数：，分别表示在它前面的小海龟数和在它后面的小海龟数。接着你发现其中有些小海龟对你撒了谎，因为根据他们的说法你根本没法给他们排队！但是你是善良的，你不希望有很多小海龟在撒谎，想找出最少有哪几只小海龟在撒谎。（注意：小海龟的名次可能是并列的！）分析：若一只海龟说了真话，那么该海龟的位置一定是在区间上。若有只海龟选择了相同的区间，则根据并列关系，该区间最多能同时拥有只海龟。可以计算出每个区间最多能有多少只海龟，把数值看做区间的“权”。则问题转化为，在一些带权区间中，选出权和最大的区间，使它们之间不能互相重叠。算法：算出每个出现过的区间的“权”，接下来的算法就是动态规划了。先按右端点坐标从小到大排序，令为在区间左边的且与之无公共点的最大区间编号，设状态为在前个区间中可选出区间的最大权和，则状态转移方程为，说真话海龟的最大数量就是最后一个区间的值。实现：由于上述所有操作的排序关键字都在中，所以可以使用时间复杂度为的基数排序，其它各操作也均能在时间内完成（具体细节留给读者思考）。所以，总时间复杂度为。例题5.2：USACO 2005 dec silver题目大意：仓库从第秒到第秒的任意时刻都需要有人打扫，包括和，。有个工人前来应聘打扫仓库的工作，每人给出自己可以工作的时间段：从第秒到第秒（包括第秒和第秒），需要支付工资元。，。每个应聘者，你能够录用或者不录用，但不能只雇佣他提出的一部分时间。一旦录用，你就得支付他提出的元给他。现在要保证从秒到第秒的任意时刻都得有人打扫，问最少要付多少工资。分析：将每个人的打扫时间看作一个左右端点分别为和，且权为区间。则问题转化为：选出一些区间，使它们覆盖上的所有整数点，求权和最小值。算法：这道题很容易想到一个的动态规划算法。将所有区间按右端点坐标从小到大排序，顺序处理每个区间。用表示在前个区间中选择，且第个区间必须选时，覆盖的权和最小值。则状态转移方程为：,最后的结果就是。第一种优化：对于这个状态转移方程，很容易想到用线段树优化的方法。建立一棵范围是的线段树，叶子节点是一个个整点坐标。每得到一个的值，就将它插入在处，并更新最小值。计算的值时只要选取区间中的最小值进行状态转移即可。算法时间复杂度为：排序+维护线段树=，故总时间复杂度是。这样做编程复杂度较高，且时间效率亦不是很好（虽然可以通过离散化稍微降低一点时间复杂度，但仍然系数巨大）。仔细分析，可以找到更好的优化方法。第二种优化：建立一个栈，表示处在栈中第个位置的区间。假设栈中已经有个区间，保持栈中区间值的单调性：。每次要将第个区间压入栈中时，做这样的操作：while poppush 计算的值时，可以借助栈找到一个区间，使且最小，进行状态转移。根据栈中元素的单调性，这里可以用二分查找。由于一共个区间，每个区间进栈、出栈最多一次，故栈的维护的时间复杂度为。在任何时间内，栈内区间个数不超过，故一次二分查找复杂度为。综上所述，该方法的总时间复杂度为。由于栈、二分查找的系数比线段树小很多，且栈内区间个数很少有达到的情况，故这种优化比前面的要好很多。第三种优化：以左端点为关键字从小到大排序，按顺序依次处理每个区间。维护一个以为关键字的优先队列。处理区间时，只要最小关键字区间的右端点坐标小于，就删除。重复上述操作，直到当前区间能和最小关键字区间进行状态转移。状态转移后，将区间插入优先队列。由于每个区间最多只进出队列一次，故一共要进行次插入操作和次删除操作。用二叉堆实现该优先队列，插入和删除操作的时间复杂度都是，因此总时间复杂度为：排序+动态规划+维护二叉堆=。该优化时间复杂度的系数介于前两种优化之间，然而对于实现而言，使用Pascal的编程量和用第一种优化差不多，而使用C/C+就可以大大减少编程量。6.区间和点的有关问题有个区间，个点。若某区间包含了某点，则构成一对匹配关系。选出最多的区间和相同数量的点，使对应的区间和点构成匹配关系。该问题虽然可以建立一个二分图匹配模型，但时间复杂度显然太高，应该充分利用区间的性质。算法：将所有的点按坐标从小到大排序，顺序处理每个点。每次都在剩余区间中取出包含该点且右端点坐标最小的区间与之配对，若没有则不选择该点。证明：设某最优解的匹配集合为，该算法求出的一对匹配是第个点和第个区间。命题6.1 和至少有一个出现在里。假设它们都不出现在里，则中还可以加上一对新的匹配，与为最优解矛盾。命题6.2 该算法求出的所有匹配都可以出现在另一最优解中。仍然考虑该算法求出的任意匹配，若，则可分以下三种情况讨论：若出现在里、未出现在里，设中与匹配。在中可删除，并添加。若出现在里、未出现在里，设中与匹配。在中可删除，并添加。若和都出现在里，设中与匹配、与匹配。根据该算法，显然有，所以可将的这两组匹配改为和。因此解可经过一系列的转化变成解，且由于转化时匹配数始终保持不变，所以也为最优解，因此该算法中的所有匹配都在其中。根据该算法，显然不可能有匹配在中却不在该算法所求出的匹配中，故该算法求出的匹配集就是，为一最优解。实现：选点时直接模拟的时间复杂度为，可用与例题5.2的优化3相似的方法来对该算法进行优化。做预处理，以区间左端点为关键字，对它们排序，得到一个有序表。维护一个优先队列，以区间的右端点作为关键字。将所有点按坐标从小到大排序，依次处理各点。处理某点时，先插入左端点小于等于该点坐标且从未进入过队列的区间（插入区间顺序和有序表一致，故每次可在时间内判断是否需要插入），再删除右端点小于该点坐标的区间，将优先队列里的区间中右端点坐标最小的与该点匹配并删除。由于每个区间只进出队列一次，故一共要进行次插入操作和次删除操作。用二叉堆实现该优先队列，则每次操作的时间复杂度降为。因此，该算法总的时间复杂度为：计算有序表+点排序+维护优先队列+处理每个点=。例题6.1：CEOI 2004 trips题目大意：有个团队和条旅行线路，每个团队最多只能选一条旅行线路，每条旅行线路至多只能供一个团队选择。第个团队有人数，第条旅行线路有人数下限和上限，只有当时，第个团队才能选择第条旅行线路。求团队和旅行线路的最大配对数。分析：将团队能去的旅行线路看作区间，将每条旅行线路看做点。转化后的问题和原问题完全一样，这里就不再写算法了。例题6.2：CEOI 2000 Enlightened Landscape题目大意：在一片山的上空，高度为处有个处于不同水平位置的灯泡（如图）。如果山的边界上某一点与灯的连线不经过山上的其他点，我们称灯可以照亮该点。开尽量少的灯，使得整个山景都被照亮。山景是一条折线，折点数。算法：容易看出，照亮整个山景的充分必要条件是照亮所有的折点。我们可以在的时间内算出某灯泡是否能照亮某折点。由于每个灯泡照射到的折点是非连续的，较难处理，我们不妨考虑每个折点能被那些灯泡照到，发现都是连续的段。于是题目转化为：给定个区间，以及个点，区间的两端点都是这个点之一。选出最少的点，使每个区间都至少包含一个所选的点。显然那些包含其它区间的区间已不必考虑，可以删去。这一步可以这么实现：将所有区间按右端点从小到大，若右端点相同则按左端点从大到小排序，从前往后依次处理。维护一个值，记录当前已处理区间左端点坐标的最大值，初始值为。处理某个区间时，若该区间的左端点小于等于，则删除该区间，否则更新。将剩余区间按位置重新排序，顺序处理各区间。若区间已包含某点，则不去考虑，否则选择区间的右端点。优化：若确定了区间，则接下来选点的复杂度显然为,时间效率的优劣取决于预处理每个折点能被哪段灯泡照到的时间。如果直接模拟，时间复杂度为，对该题的数据规模而言，这个算法已经可以AC了。其实可以用栈将预处理的时间复杂度进一步降低：先从左往右扫描，确定每个折点能被最左边的哪个灯泡照到。对于第折点，进行这样的操作（设栈中有个元素）：while折点的高度大于等于折点的高度or 线段（折点，折点）在折点上方pop算出射线（折点，折点）与直线的交点利用二分查找找到横坐标大于等于的最左边的灯泡（该灯泡就是能照到折点的最左边的灯泡）push 同样可以通过从左往右扫描求出每个折点能被最右边的哪个灯泡照到。由于每个折点最多进出栈一次，栈的维护需要的时间为，故预处理时间复杂度为：栈操作+二分查找=，总时间复杂度也就降为。【总结】区间问题通常要保持有序性，排序关键字的选择非常重要。只有选择了合适的关键字，才更容易解决这类问题。区间问题的解决方法主要有两种：贪心（构造）；动态规划。虽然后者能解决更多的问题，但往往前者拥有更好的时间效率，实现或优化起来更加容易。区间问题的优化大多可以用到线段树，极少数要用到平衡二叉树，但往往这并不是最佳的优化方法。要学会在解题过程中发现更好的规律，用编程复杂度和时间效率俱佳的方法进行优化，如利用决策的单调性，或运用一些简单数据结构维护等。【参考文献】1算法艺术与信息学竞赛 刘汝佳 黄亮 著 清华大学出版社2计算机算法设计与分析 王晓东编著 电子工业出版社3算法设计 Jon Kleinberg，va Tardos 著 清华大学出版社4广东省大学生程序设计竞赛试题（2003-2005年）郭嵩山 黎俊瑜 林祺颖 著 电子工业出版社5CTSC 2007 Reports, By Guo Huayang6汪汀turtle解题报告2005集训队作业7. 朱晨光基本数据结构在信息学竞赛中的应用 2006集训队论文【附录】Latin America - South America 2001 Problem AGene AssemblyWith the large amount of genomic DNA sequence data being made available, it is becoming more important to find genes (parts of the genomic DNA which are responsible for the synthesis of proteins) in these sequences. It is known that for eukaryotes (in contrast to prokaryotes) the process is more complicated, because of the presence of junk DNA that interrupts the coding regions of genes in the genomic sequence. That is, a gene is composed by several pieces (called exons) of coding regions. It is known that the order of the exons is maintained in the protein synthesis process, but the number of exons and their lengths can be arbitrary.Most gene finding algorithms have two steps: in the first they search for possible exons; in the second they try to assemble a largest possible gene, by finding a chain with the largest possible number of exons. This chain must obey the order in which the exons appear in the genomic sequence. We say that exon appears before exon j if the end of i precedes the beginning of j. The objective of this problem is, given a set of possible exons, to find the chain with the largest possible number of exons that could be assembled to generate a gene.InputSeveral input instances are given. Each instance begins with the number 0 n 1000 of possible exons in the sequence. Then, each of the next n lines contains a pair of integer numbers that represent the position in which the exon starts and ends in the genomic sequence. You can suppose that the genomic sequence has at most 50000 basis. The input ends with a line with a single 0.OutputFor each input instance your program should print in one line the chain with the largest possible number of exons, by enumerating the exons in the chain. The exons must follow the order of appearance (as defined in the statement of the problem). If there is more than one chain with the same number of exons, your program can print anyone of them.Sample Input6340 500220 470100 300880 943525 556612 7763705 773124 337453 66502Sample Output3 1 5 6 42 3 1（例题1）North America Northeast 2003 Problem EWho is Still Alive?At various points in history a number of presidents (former and the current president) have been alive. For example, currently there are six living presidents: Ford, Carter, Reagan, George the Second (George H. Bush), Clinton, and George the Third (George W. Bush). Note: George Washington was George the First.Write a program that takes as input the name, inauguration date, and date of death (if appropriate) of several presidents and produces as output the periods of time when the maximum number of current or former presidents are alive, together with the names of those presidents in alphabetical order. Note, there may be several such intervals and all must be listed in chronological order.InputThe input to your program will start with a line that contains a single integer, N, that specifies the number of presidents to be considered. Each of the following N lines of input describes a single president. An input line for a president will consist of an identifier consisting of letters only. The identifier will be followed by the inauguration date, and by an optional date of death. Dates will be expressed in the form yyyy - mm - dd where yyyy represents a year, mm represents a month, and dd represents a day. If the president is still alive, no death date will be given. One or more white space characters will separate tokens on the input line. Note that if a president was inaugurated more than once, they may appear in the input more than once; remember, however, that once a president, always a president.OutputThe output from the program will specify the period of time when the most presidents were alive, followed by the names in alphabetical order. If there are multiple intervals, the intervals will be listed in chronological order, separated by a blank line. Sample Input3Nixon 1969-01-20 1994-04-22Ford 1974-01-20GWBush 2001-01-20Sample Output1969-1-20 to 1994-4-22FordNixon1974-1-20 to 2003-11-7FordGWBush（问题2中曾提到）2004年广东省大学生程序竞赛试题 Problem BBerth Allocation(Input File: berth.in/Output File: berth.out)Singapore port is one of the busiest ports in the world. In 1994, Singapore maintained its position as the worlds busiest port in terms of shipping tonnage of ship arrivals. In that year, there were 101,107 ship arrivals with shipping tonnage of 678.6 million gross tons. One of the planning problems encountered at the post is to decide whether a given set of ships can be berthed in a section of the port with certain berthing constraints.The port is divided into m sections and no ship can berthed across a section. Ships arrive at the port at different times to be berthed. Every ship has an expected duration of stay which may be different from another ship. You can berth a ship or not when it arrives. To berth a ship is to place the ship along the wharf line of a section. Once a ship if berthed, it will not be moved until its departure, that is, if two ships are in the same section and have a time overlap, they cannot share any part of the section. Whats more, the berthing of the ships cannot exceed the capacity of the section.To simplify the problem, we just consider the section as a rectangle with a length of L hundred meters and a width of W hundred meters. When a ship arrives, you can berth it at any available position in the section at that time, or you can reject berthing it according to your berthing plan. Now the problem becomes a packing model of 3 dimensions (length, width, time). Since the width of a section if the same as ships, we can just consider the problem in 2 dimensions (length, time).Here is the explanation of the last data set in the sample input. The port has one section, which is 2 hundred meters long. There are four ships arriving at time 1,5,2,4 and departing at time 3,6,8,10 respectively. They are all berth in section one. Figure 2.2.1 and Figure 2.2.2 are two legal berthing plans, from which we can know the maximal number of berthed ships is 3.Figure 2.2.1 The Berthing Plan of 3 shipsFigure 2.2.2 The other Berthing Plan of 3 shipsMax, the consultant of the harbor bureau, thinks that it is a ZSU(Zappy Ships Unallocation) problem. As his name, Max wants to make a plan to maximize the total number of berthed ships, in other words, minimize the number of unberthed ships. Just like other packing problems, it is difficult for Max to solve. But he believes that the best team of the contest is able to solve it both correctly and effectively. Do your guys want to be the best? Just try it.Input:Input contains many test sets. A test data set is defined as follow:The first line of test data set is two integers: m and n, separated by one or more spaces(1m10, 1n100000). m is the number of sections in the port, and n is the number of ships.The next m lines, one positive integer r (that means the length of the section is r hundred meters long) per line. The length of each section does not exceed 10000 hundred meters.The next n lines gives one ship information on each line, with three non-negative integers s, e, sec (0se,1secm) per line, s is the arrival time of the ship, e is the departure time of the ship, and sec is the section which the ship should be berthed in.Input is ended by EOF. You can assume that all the input data are legal.Output:For each test data set you should output one integer, the maximal number of the berthed ships, per line.Sample Input:2 6331 2 11 2 11 2 11 2 11 2 21 2 21 321 3 12 6 12 8 11 421 3 15 6 12 8 14 10 1Sample Output:523（例题2）CTSC 2007 DAY2 pendant挂缀【问题描述】“珠缀花蕊，人间几多酸泪”挂缀在很早就被人们作为一种装饰品，垂坠的风韵，华丽摇曳的摆动，展现出一种与众不同的优雅与高贵。而我们的主人公小Q，正想买一条漂亮的挂缀放在寝室里作为装饰。挂坠的构成，是由若干粒缀珠相互连接而成。每一个缀珠由三部分组成：分别是珠子、珠子上方的连接环与珠子下方的挂钩（如下图）。我们可以简单的认为从上往下数的第i 个缀珠是将它的连接环套在其上方（也就是第i-1 个）缀珠的挂钩之上（第一个除外）。小Q 想买一根足够长的挂缀，这样显得更有韵味然而商店的老板告诉小Q，挂缀是不可能做到任意长的，因为每一个珠子都受到重力作用，对其上方的挂钩有一定的拉力，而挂钩的承受能力是有限的。老板还告诉小Q，他一共拥有N 个珠缀（假设每一个珠缀都很漂亮，小Q 都很喜欢），每个珠缀都有其各自的重量与承受能力。一个挂缀是稳定的，当且仅当对于其上的每一个珠缀，它下方所有珠缀的重量和（不包含自身）不超过其挂钩的承受能力。小Q 希望她的挂缀尽量长，你能帮她计算出最长可能的稳定挂缀么？当然，如果有多个可选解，小Q 希望总重量最小的。【输入文件】输入文件pendant.in 第