leetcode 合并区间
时间: 2023-08-02 11:04:52 浏览: 277
linxid#Leetcode_Python#56.合并区间1
合并区间是一道经典的算法题,可以用来合并重叠的区间。下面是一种常见的解题思路:
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
```
希望对你有帮助!如果还有其他问题,请随时提问。
阅读全文