0x09 区间合并
[toc]
1. 什么是区间合并
区间合并就是把多个区间，有可能有重叠部分，如果有重叠部分，那就合并成一个区间。最终求出合并为几个区间。
那么区间合并有啥用呢，其实我也不知道有啥用，可能这本身能出一道题吧。
2. 如何区间合并
首先想到朴素方法，二重循环遍历所有情况，时间复杂度是O(n^2^)。
如果我们将区间排序，遍历所有区间，下一个区间和当前区间就有两种情况，
- 和当前区间有重叠部分，这种情况可以直接合并区间。
- 在当前区间内部重叠（当前区间完全覆盖该区间）
- 在当前区间外部重叠（区间的起始位置在当前区间中）
- 不存在区间的起始位置在当前的区间之前的，因为排过序
- 无重叠部分，即区间的起始位置大于当前区间的终止位置。那么就说明该区间以及之后的所有区间都和当前区间无交集（因为有序）。可以直接将这个区间提交到合并好的区间数组，把当前区间换成下一个区间。
这样最终的时间复杂度为O(n*logn）。 (n*log n 是排序时间，远大于后面比较的时间n)
最后更新:
May 29, 2022