区间合并算法 题目描述 给定一个区间集合，每个区间表示为 [ start, end ]，其中 start 和 end 分别是区间的起点和终点。要求合并所有重叠的区间，并返回一个不重叠的区间集合，该集合需覆盖输入中的所有区间。 例如： 输入：[ [ 1,3], [ 2,6], [ 8,10], [ 15,18] ] 输出：[ [ 1,6], [ 8,10], [ 15,18] ] 解释：区间 [ 1,3] 和 [ 2,6] 重叠，合并为 [ 1,6 ]。 解题步骤 排序区间 首先将所有区间按照起点（start）从小到大排序。 目的：确保重叠的区间在排序后相邻，便于顺序处理。 示例：输入 [ [ 2,6], [ 1,3], [ 15,18], [ 8,10]] 排序后为 [ [ 1,3], [ 2,6], [ 8,10], [ 15,18] ]。 初始化结果列表 创建一个空列表（如 merged ）用于存储合并后的区间。 将第一个区间直接加入 merged （因为它是当前唯一的区间）。 遍历并合并区间 从第二个区间开始，依次与 merged 中最后一个区间比较： 如果当前区间与最后一个区间不重叠 （即当前区间的起点 > 最后一个区间的终点），直接将当前区间加入 merged 。 如果重叠 （即当前区间的起点 ≤ 最后一个区间的终点），合并两个区间：将 merged 中最后一个区间的终点更新为两个区间终点的最大值。 重复此过程直到遍历完所有区间。 示例分步演示 输入：[ [ 1,3], [ 2,6], [ 8,10], [ 15,18] ] 排序后：[ [ 1,3], [ 2,6], [ 8,10], [ 15,18] ]（已有序）。 步骤： 将 [ 1,3] 加入 merged → merged = [[1,3]] 。 检查 [ 2,6]：起点 2 ≤ 终点 3（重叠），合并为 [ 1, max(3,6)=6] → merged = [[1,6]] 。 检查 [ 8,10]：起点 8 > 终点 6（不重叠），直接加入 → merged = [[1,6], [8,10]] 。 检查 [ 15,18]：起点 15 > 终点 10（不重叠），直接加入 → merged = [[1,6], [8,10], [15,18]] 。 关键点 排序确保重叠区间相邻，降低问题复杂度至 O(n log n)。 合并时只需比较当前区间与 merged 最后一个区间，因为排序后后续区间起点必然更大。