华为机试【3、区间交集】

3、标题:区间交集
【区间交集】给定一组闭区间，其中部分区间存在交集。任意两个给定区间的交集，称为公共区间(如:[1,2],[2,3]的公共区间为[2,2]，[3,5],[3,6]的公共区间为
[3,5])。公共区间之间 若存在交集，则需要合并(如:[1,3],[3,5]区间存在交集[3,3]，需合并为[1,5])。按升序排列 输出合并后的区间列表。
输入描述: 一组区间列表，区间数为 N: 0<=N<=1000;区间元素为 X: -10000<=X<=10000。
输出描述: 升序排列的合并区间列表
备注:
1、区间元素均为数字，不考虑字母、符号等异常输入。
2、单个区间认定为无公共区间。
示例:
输入
[[0, 3], [1, 3], [3, 5], [3, 6]]
输出
[[1, 5]]

def common_section_merge(arr):
    if len(arr) == 1:
        return arr[0]
    arr.sort(key=lambda x: x[0])  # 区间列表按区间开头从小到大排序
    comm_section = []  # 公共区间列表
    # 两两对比取出所有交集列表
    for i in range(len(arr) - 1):
        for j in range(i + 1, len(arr)):
            if arr[i][-1] >= arr[j][0]:  # 存在交集
                comm_section.append([arr[j][0], min(arr[i][-1], arr[j][-1])])
    if len(comm_section) == 1:
        return comm_section
    comm_section.sort(key=lambda x: x[0])
    l = len(comm_section)
    i = 0
    # 合并交集列表之间的公共区间
    while i <= l - 2:
        if comm_section[i][-1] >= comm_section[i + 1][0]:
            comm_section[i][-1] = max(comm_section[i][-1], comm_section[i + 1][-1])
            comm_section.pop(i + 1)
            l -= 1
        else:
            i += 1
    return comm_section


print(common_section_merge([[0, 3], [1, 3], [3, 5], [3, 6]]))