【LeetCode】0056&0057 合并区间&插入区间

https://leetcode-cn.com/problems/merge-intervals/

# -*- coding:utf-8 -*-

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        def cmp(x, y):
            if x[0] > y[0]:
                return 1
            elif x[0] < y[0]:
                return -1
            else:
                return 0
        if len(intervals) == 1:
            return intervals
        import functools
        intervals = sorted(intervals, key=functools.cmp_to_key(cmp))
        do_length = 0
        do_idx = 1
        max_length = len(intervals)
        while do_length < max_length - 1:
            if intervals[do_idx][0] <= intervals[do_idx - 1][1]:
                intervals[do_idx - 1][1] = max(intervals[do_idx][1], intervals[do_idx - 1][1])
                intervals.remove(intervals[do_idx])
            else:
                do_idx += 1
            do_length += 1
        return intervals
if __name__ == '__main__':
    intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
    intervals = [[1, 3], [5, 6]]
    # intervals = [[1, 4], [0, 2], [3, 5]]
    print(Solution().merge(intervals))

思路：首先是排序，然后根据当前的0号位是否小于前一个的1号位来判断这两个是否可以合并，如果可以就合并。

这里了解了python的自定义比较函数，还必须导入一个funtools。。学到了学到了。

插入区间只要在上面代码上做一些微小的改动，将newInterval插入intervals然后改一下边界条件即可。

# -*- coding:utf-8 -*-

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        def cmp(x, y):
            if x[0] > y[0]:
                return 1
            elif x[0] < y[0]:
                return -1
            else:
                return 0
        if len(intervals) == 0:
            return [newInterval]
        import functools
        intervals.append(newInterval)
        intervals = sorted(intervals, key=functools.cmp_to_key(cmp))
        do_length = 0
        do_idx = 1
        max_length = len(intervals)
        while do_length < max_length - 1:
            if intervals[do_idx][0] <= intervals[do_idx - 1][1]:
                intervals[do_idx - 1][1] = max(intervals[do_idx][1], intervals[do_idx - 1][1])
                intervals.remove(intervals[do_idx])
            else:
                do_idx += 1
            do_length += 1
        return intervals
if __name__ == '__main__':
    intervals = []
    newInterval = [5, 7]
    print(Solution().insert(intervals, newInterval))