区间合并问题题解

思路

若区间已经按照左端点从小到大排列，当前尚未输出的合并区间记为 $[l,r]$。依次考察下一个区间 $[L,R]$：当 $L\le r$ 时，两者有公共点，应把右端点更新为 $\max(r,R)$；当 $L>r$ 时，两者不相交，当前区间已经确定，可以输出它并开始维护新区间。

原输入未保证有序，因此先按左端点升序、右端点升序排序，再执行上述扫描。

做法

读入所有区间并排序。用第一个区间初始化当前合并区间，随后从第二个区间开始扫描。遇到相交区间就扩展当前右端点，遇到不相交区间就保存当前结果并重新初始化。扫描结束后，再保存最后一个当前区间，最后按顺序输出全部结果。

正确性证明

排序后，尚未处理区间的左端点都不小于当前考察区间的左端点。

若下一个区间左端点不大于当前右端点，则两个闭区间相交，它们的并集仍是一个闭区间。把当前右端点更新为两者右端点的最大值，恰好得到它们的并集，不会改变已经覆盖的点。

若下一个区间左端点大于当前右端点，则由于后续区间的左端点只会更大，任何后续区间都不可能与当前区间相交。因此当前区间必然是最终表示中的一个区间，此时输出它是安全且必要的。

由上述过程归纳可知，扫描结束后得到的区间并集与原区间并集完全相同，且任意相邻两个结果区间都不相交。任何表示原并集的方案都必须分别覆盖这些互不相交的连通部分，所以不能使用更少的区间；本算法得到的方案所含区间数量最少。

复杂度

排序耗时 $O(n\log n)$，扫描耗时 $O(n)$，总时间复杂度为 $O(n\log n)$；保存输入和答案的空间复杂度为 $O(n)$。