56合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

提示：

intervals[i][0] <= intervals[i][1]

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/merge-intervals 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

排序+一遍去重

class Solution:
    def merge(self, intervals: [[int]]) -> [[int]]:
        # need to be qick sort
        intervals.sort()
        lengthDIfOne = len(intervals) - 1
        i = 0
        while(i < lengthDIfOne):
            if intervals[i][1] >= intervals[i+1][0]:
                temp = intervals.pop(i+1)[1]
                lengthDIfOne -= 1
                if intervals[i][1] < temp:
                    intervals[i][1] = temp
            else:
                i += 1
        return intervals

Solution 1

排序+一遍去重
排序为自己写的qsort

class Solution:
    def merge(self, intervals: [[int]]) -> [[int]]:
        # need to be qsort()
        self.qsort(intervals, 0, len(intervals)-1, lambda x, y: x[0] <= y[0])
        lengthDIfOne = len(intervals) - 1
        i = 0
        while(i < lengthDIfOne):
            if intervals[i][1] >= intervals[i+1][0]:
                temp = intervals.pop(i+1)[1]
                lengthDIfOne -= 1
                if intervals[i][1] < temp:
                    intervals[i][1] = temp
            else:
                i += 1
        return intervals

    def qsort(self, array, left, right, cmp=lambda x, y: x <= y):
        if (left >= right):
            return
        i = left
        j = right
        temp = array[left]
        while(i < j):
            while (i < j and cmp(temp, array[j])):
                j -= 1
            array[i] = array[j]
            while (i < j and cmp(array[i], temp)):
                i += 1
            array[j] = array[i]
        array[i] = temp
        self.qsort(array, left, i-1, cmp)
        self.qsort(array, i+1, right, cmp)