难度: Medium
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104注意：本题与主站 56 题相同： https://leetcode-cn.com/problems/merge-intervals/
运行时间: 26 ms
内存: 17.4 MB
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
# 先将区间按照其左端点排序
n = len(intervals)
if n==1: return intervals
intervals.sort(key=lambda x:x[0])
ans = []
begin, end = intervals[0]
for i in range(1,n):
a,b = intervals[i]
if a<=end:
if b>end: end = b
else: # a>end
ans.append([begin, end])
begin, end = a, b
# 把最后一组 begin,end 加到答案中
ans.append([begin, end])
return ans
The solution involves sorting the list of intervals based on the start time of each interval to ensure that any potentially overlapping intervals are next to each other. After sorting, the algorithm initializes the first interval as the current range to merge other intervals into. For each subsequent interval, it checks if there is an overlap with the current range (i.e., the start of the next interval is less than or equal to the end of the current interval). If they overlap, the end of the current merged interval is updated if necessary. If there is no overlap, the current merged interval is complete and added to the results list, and a new current interval is started with the non-overlapping interval. This process is repeated for all intervals. Finally, the last merged interval is added to the results list.
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
# Check if there's only one interval, return it directly
n = len(intervals)
if n == 1: return intervals
# Sort intervals based on the start of each interval
intervals.sort(key=lambda x: x[0])
ans = []
begin, end = intervals[0]
# Iterate through each interval to merge
for i in range(1, n):
a, b = intervals[i]
if a <= end:
# There is an overlap, so merge the intervals
if b > end: end = b
else:
# No overlap, add the current interval to the answer
ans.append([begin, end])
begin, end = a, b
# Add the last processed interval to the list
ans.append([begin, end])
return ans
将区间按起始位置排序是为了将所有可能重叠的区间置于相邻的位置，从而便于合并。排序后，可以顺序遍历区间列表，连续处理并合并所有重叠的区间。如果不进行排序，重叠的区间可能会散布在列表中的不同位置，这将使得合并过程变得复杂且效率低下。
当区间列表中存在包含关系时，例如 [[1,4],[2,3]]，排序后这些区间仍会紧邻排列。在合并过程中，当遇到内部区间（如 [2,3]）与当前合并区间（如 [1,4]）有重叠时，算法会比较内部区间的结束位置与当前合并区间的结束位置。如果内部区间的结束位置在当前合并区间的结束位置之内，合并操作只需维持当前合并区间的边界；因此，包含关系的区间被正确处理，合并结果为 [1,4]。
对于边界相接但不重叠的区间，如 [[1,2],[3,4]]，算法在处理时会识别出这些区间之间没有重叠（即下一个区间的起始位置大于当前合并区间的结束位置）。因此，每个区间会被视为独立的区间加入到结果列表中。在这个例子中，输出结果将会是 [[1,2], [3,4]]，即保持区间的独立性，不进行合并。