第八天：《LeetCode一天一例》-----区间的合并（python实现）

古城微笑少年丶 2022-03-07 06:22 217阅读 0赞

# 区间的合并 #

>         题目：\[\[2, 5\], \[1, 3\], \[5, 9\], \[10, 29\], \[12, 20\]\]   这个列表中嵌套了好多列表，里面的每一个列表代表一个区间。。我们要将它们合并。 看下图：
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70][]
> 
>     分别画出是哪个区间的位置，然后公共的位置合并 。。最后三个区间合并为一个区间 。。后面两个也可以采用相同思路

### 分析：    ###

我们这里先将各个区间按第二位（也就是右端点的值）进行排序。  为什么要这样做？  如果排序了，两个区间合并，我们就不必考虑上界了，肯定是后面区间的右端点。 但下界不能确定，有可能是前一个区间的左端点，也有可能是后面区间的左端点。。  此时我们要分情况了：

***情况一：***将前一个区间的左端点和后一个区间的左端点进行比较，后一个区间的左端点比前一个区间的左端点还小，说明前一个区间是后一个区间的子区间，直接将第一个区间踢出去就行

***情况二：***如果不满足第一种情况，我们就得考虑这两个区间是否有交集，怎样判断呢？  只需将前一个区间的右端点和后一个区间的左端点进行比较，若前一个区间的右端点比后一个区间的左端点大的话，说明有交集。。我们用前一个区间的左端点和后一个区间的右端点构造一个新的区间，将这个新区间添加到列表中，删除被合并的两个区间。

***情况三：***情况一，情况二都不满足的情况下，我们只能再往后看其他区间

### 代码实现： ###

def sort(con):
        # 1.把每个区间按后一个值进行排序  这里采用冒泡的思想
        for i in range(len(con)-1, -1, -1):
            sign = False
            for j in range(0, i):
    
                if con[j][1] > con[j+1][1]:
                    temp = con[j][1]
                    con[j][1] = con[j+1][1]
                    con[j+1][1] = temp
                    sign = True
            if sign == False:
                break
        return con
    
    def concrete(sort_con):
        # 接着我们进行区间的合并
    
        # 1.我们判断前一个区间的第二值和后一个区间的第一个值
        i = 0
        while i <= (len(sort_con)-2):
            if sort_con[i][0] >= sort_con[i+1][0]:
                # 这个说的就是前一个区间的左端点都大于后一个区间的左端点  说明前一个区间在后一个区间的里面
                # 这个是时候的处理就是删掉前一个区间
                sort_con.remove(sort_con[i])
                continue
            elif sort_con[i][1] >= sort_con[i+1][0]:    # 此时我们再比较前一个区间的右端点是否大于后一个区间的左端点
                # 如果成立 进行合并
                temp = [sort_con[i][0], sort_con[i+1][1]]  # 前一个区间的左和后一个区间的右合成一个新区间
                sort_con.remove(sort_con[i])
                sort_con.remove(sort_con[i])   # 删除i为后，后一个元素往前移动 也就变成了第i位元素
                sort_con.insert(i, temp)
                continue
            else:
                i += 1
        return sort_con
    
    if __name__ == '__main__':
        # 下面列表中给出了一些区间， 我们现在进行求交
        con = [[2, 5], [1, 3], [5, 9], [10, 29], [12, 20]]
        # con = [[4, 6], [2, 5], [5, 9], [1, 6], [8, 17], [4, 9], [11, 20]]
        sort_con = sort(con)
        print(sort_con)   # 按照区间的第二值进行排序  不会漏到一些点
    
        result = concrete(sort_con)
        print(result)

### 结果输出： ###

![20190316123951665.png][]

方法二：

def qujian_concat(con):
        con.sort(key=lambda x: x[0])
        result = []
        cur_start = con[0][0]
        cur_end = con[0][1]
        for item in con[1:]:
            if item[0] <= cur_end:
                cur_end = max(cur_end, item[1])
    
            else:
                result.append([cur_start, cur_end])
                cur_start = item[0]
                cur_end = item[1]
    
        result.append([cur_start, cur_end])
        print(result)
    
    
    if __name__ == '__main__':
        # 下面列表中给出了一些区间， 我们现在进行求交
        con = [[2, 5], [1, 3], [5, 9], [10, 29], [12, 20]]
        qujian_concat(con)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70]: /images/20220307/dbc864bfaaac45ea8f348bea97710256.png
[20190316123951665.png]: /images/20220307/231726fa0c5e4b499bf08203e770594c.png