合并区间问题

题解思路

本题的核心在于区间合并，首先要对区间进行排序，然后通过遍历并合并相邻区间的方式来消除重叠的部分。

具体步骤如下：

1. 排序：首先按照区间的起点 start 进行升序排序，如果 start 相同，则按照 end 排序（默认即可）。
2. 合并区间：
   • 使用一个 merged 列表存储合并后的区间。
   • 遍历排序后的区间：

Leetcode 14.合并区间-原题链接

题目内容

以数组 $intervals$ 表示若干个区间的集合，其中单个区间为 $intervals[i] = [start_i, end_i]$ 。请你合并所有重叠的区间，并输出一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

输入描述

第一行为一个整数 $n$ ，代表数组 $intervals$的长度。 接下来的$n$行，每行有两个整数$start_i, end_i$，代表第$i$个区间。

输出描述

如题，每行输出一个区间，区间的数字以空额分隔。每个区间以$start_i$升序输出。

样例1

输入

4
1 3
2 6
8 10
15 18

输出

1 6
8 10
15 18

说明

区间 $[1,3] 和 [2,6]$重叠, 将它们合并为$[1,6]$

样例2

输入

2 
1 4
4 5

输出

1 5

说明

区间$[1,4]$和 $[4,5]$ 可被视为重叠区间。

提示

• $1 <= intervals.length <= 10^4$
• $intervals[i].length == 2$
• $0 <= start_i <= end_i <= 10^4$