如何基于‘end+1等于start’条件最优实现区间合并？

核心思路依然是排序后线性遍历，这是区间合并问题的最优解法，时间复杂度为O(n log n)（排序占主导），远优于遍历所有区间对的O(n²)方案。

你之前认为“排序后符合条件的区间未必相邻”是误解——按区间起始值升序排序后，所有可合并的区间（包括满足前一个区间end+1等于后一个区间start的情况）都会在遍历过程中被依次处理，因为合并后的区间会不断扩展其结束值，后续只要有区间的起始值不超过当前合并区间的结束值+1，就会被合并。

修改后的代码 #

from typing import List

def merge(intervals: List[List[int]]) -> List[List[int]]:
    if not intervals:
        return []
    
    # 按区间起始值升序排序
    intervals.sort()
    result = []
    prev_start, prev_end = intervals[0]
    
    for curr_start, curr_end in intervals[1:]:
        # 判断条件调整：前一个区间的end+1 >= 当前区间的start时触发合并
        if prev_end + 1 >= curr_start:
            # 合并后保留最大的结束值
            prev_end = max(prev_end, curr_end)
        else:
            # 无法合并，将当前已合并的区间存入结果
            result.append([prev_start, prev_end])
            prev_start, prev_end = curr_start, curr_end
    
    # 存入最后一个合并完成的区间
    result.append([prev_start, prev_end])
    return result

示例验证 #

• 示例1：merge([[1,2], [3,4]]) → [[1,4]]，符合预期
• 示例2：merge([[1,5], [6,9]]) → [[1,9]]，符合预期
• 示例3：merge([[1,5], [14, 17], [6,9], [10,13]]) → [[1,17]]，符合预期
• 示例4：输入[[1,5], [14, 17], [6,9], [10,13], [4,7], [8,12]]实际会合并为[[1,17]]，你提供的示例4输出可能存在笔误，所有输入区间可通过连续合并形成一个整体。

内容的提问来源于stack exchange，提问作者bbasaran