补充

一些基本算法的补充知识。

区间合并

区间合并是指对给定的一组区间进行合并，将其中重叠且连续的区间合并成一个或多个新的区间。

先按照区间左端点进行排序，然后从左到右遍历区间，如果相邻两个区间有重叠部分，则将它们合并成一个更大的区间。具体实现可以考虑使用一个辅助栈来存储区间，遍历到一个新的区间时，判断它是否与栈顶区间有重叠部分，如果有，则将它们合并成一个更大的区间再压入栈中，否则直接将新区间压入栈中。

def merge_intervals(intervals):
    # 根据区间左端点排序
    intervals.sort(key=lambda x: x[0])
    stack = []
    for i in range(len(intervals)):
        if not stack or intervals[i][0] > stack[-1][1]:
            # 如果集合为空或者当前区间与栈顶区间不重叠，则将当前区间压入栈中
            stack.append(intervals[i])
        else:
            # 否则将当前区间与栈顶区间合并成一个更大的区间
            stack[-1] = (stack[-1][0], max(stack[-1][1], intervals[i][1]))
    return stack