leetcode 合并区间
时间: 2023-08-02 22:04:52 浏览: 94
合并区间是一道经典的算法题,可以用来合并重叠的区间。下面是一种常见的解题思路:
1. 首先,按照区间的起始位置进行排序,这样可以确保相邻的区间有序。
2. 创建一个空的结果列表,用来存储合并后的区间。
3. 遍历排序后的区间列表,依次将每个区间与结果列表中的最后一个区间进行比较。
- 如果当前区间的起始位置大于结果列表中最后一个区间的结束位置,说明它们不重叠,直接将当前区间添加到结果列表中。
- 否则,它们重叠,需要合并它们。将结果列表中最后一个区间的结束位置更新为当前区间的结束位置(取两者中较大的值)。
4. 最终,结果列表中存储的就是合并后的区间。
下面是一个示例代码实现(使用Python):
```python
def merge(intervals):
# 按照起始位置进行排序
intervals.sort(key=lambda x: x[0])
merged = [] # 结果列表
for interval in intervals:
# 如果结果列表为空或当前区间与结果列表中最后一个区间不重叠,则直接添加到结果列表
if not merged or interval[0] > merged[-1][1]:
merged.append(interval)
else:
# 否则,更新结果列表中最后一个区间的结束位置
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
```
希望对你有帮助!如果还有其他问题,请随时提问。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)