【LintCode 简单】156. 合并区间

喜欢ヅ旅行 2022-11-27 00:45 129阅读 0赞

1.问题描述：

给出若干闭合区间，合并所有重叠的部分。

2.样例：

> 样例1:
> 
> 输入: \[(1,3)\]  
> 输出: \[(1,3)\]  
> 样例 2:
> 
> 输入:  \[(1,3),(2,6),(8,10),(15,18)\]  
> 输出: \[(1,6),(8,10),(15,18)\]

3.代码：

"""
    Definition of Interval.
    class Interval(object):
        def __init__(self, start, end):
            self.start = start
            self.end = end
    """
    
    
    class Solution:
        """
        @param intervals: interval list.
        @return: A new interval list.
        """
    
        def merge(self, intervals):
            # write your code here
            if len(intervals) < 2:  # 数组长度小于2直接返回
                return intervals
            intervals = sorted(intervals, key=lambda x: x.start)  # 排序
            res = [intervals[0]]
            i = 1
            k = 0
            while i < len(intervals):
                if res[k].end >= intervals[i].start:  # 判断是否可以合并
                    res[k] = Interval(res[k].start, res[k].end if res[k].end >= intervals[i].end else intervals[i].end)
                else:
                    res.append(intervals[i])
                    k += 1
                i += 1
            return res

注意：给的原始intervals中可能并不是按照start有序排列的，所以一开始需要做一个排序的工作。这里利用sorted函数，key的话就是排序的元素，这里是需要比较start的值。

sorted(iterable, cmp=None, key=None, reverse=False)

参数说明如下：

*  iterable -- 可迭代对象。
 *  cmp -- 比较的函数，这个具有两个参数，参数的值都是从可迭代对象中取出，此函数必须遵守的规则为，大于则返回1，小于则返回-1，等于则返回0。
 *  key -- 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。
 *  reverse -- 排序规则，reverse = True 降序 ， reverse = False 升序（默认）。

在对原始intervals排序之后，就循环从第一个开始。如果interval的end小于下一个interval的start则不会进行合并，否则就需要进行合并操作。合并操作中的新interval的end需要进行判断。

参考资料：

1. [https://www.jianshu.com/p/c7b70cbb3df0][https_www.jianshu.com_p_c7b70cbb3df0]

[https_www.jianshu.com_p_c7b70cbb3df0]: https://www.jianshu.com/p/c7b70cbb3df0