[Leetcode][python]Insert Interval/插入区间

矫情吗；* 2022-06-07 05:35 152阅读 0赞

## 题目大意 ##

给出多个不重合的数据区段，现在插入一个数据区段，有重合的区段要进行合并。

注意点：  
所给的区段已经按照起始位置进行排序

## 解题思路 ##

来自：[https://shenjie1993.gitbooks.io/leetcode-python/057%20Insert%20Interval.html][https_shenjie1993.gitbooks.io_leetcode-python_057_20Insert_20Interval.html]  
最简单的方式就是复用 Merge Intervals 的方法，只需先将新的数据区段加入集合即可，但这样效率不高。既然原来的数据段是有序且不重合的，那么我们只需要找到哪些数据段与新的数据段重合，把这些数据段合并，并加上它左右的数据段即可。

## 代码 ##

### 复用Merge Intervals ###

class Solution(object):
        def insert(self, intervals, newInterval):
            """
            :type intervals: List[Interval]
            :type newInterval: Interval
            :rtype: List[Interval]
            """
            result = []
            if not intervals:
                return [newInterval]
            intervals.append(newInterval)
            intervals.sort(key = lambda x: x.start)
            result.append(intervals[0])
            for interval in intervals[1:]:
                prev = result[-1]
                if prev.end >= interval.start:
                    prev.end = max(prev.end, interval.end)
                else:
                    result.append(interval)
            return result

### 独立解法（效率较高） ###

# Definition for an interval.
    # class Interval(object):
    #     def __init__(self, s=0, e=0):
    #         self.start = s
    #         self.end = e
    
    class Solution(object):
        def insert(self, intervals, newInterval):
            """
            :type intervals: List[Interval]
            :type newInterval: Interval
            :rtype: List[Interval]
            """
            start, end = newInterval.start, newInterval.end
            left = list(filter(lambda x: x.end < start, intervals))
            right = list(filter(lambda x: x.start > end, intervals))
            print left, right
            if len(left) + len(right) != len(intervals):  # 如果左边和右边的数量相加不等于原数量，说明新区间与某个老区间有交叉，则需要合并
                start = min(start, intervals[len(left)].start)  # len(left)是分开后左边区间的后面一个
                end = max(end, intervals[-len(right) - 1].end)  # -len(right) - 1是分开后右边区间的前面一个
    
            return left + [Interval(start, end)] + right  # Interval是区间类，新建一个区间类

## 总结 ##

关于filter，`list(filter(lambda x: x.end < start, intervals))`，请看：  
[http://blog.csdn.net/shark0001/article/details/1363564][http_blog.csdn.net_shark0001_article_details_1363564]

[https_shenjie1993.gitbooks.io_leetcode-python_057_20Insert_20Interval.html]: https://shenjie1993.gitbooks.io/leetcode-python/057%20Insert%20Interval.html
[http_blog.csdn.net_shark0001_article_details_1363564]: http://blog.csdn.net/shark0001/article/details/1363564