LintCode 156. 合并区间

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

image.png
挑战
O(n log n) 的时间和 O(1) 的额外空间。
思路1
首先将原数组按照区间起点从大到小排序，新建空数组res，依次将数组首元素弹出，同res末位元素比较，如果区间重合着将合并后的新区间替代末位元素，否则res追加该元素。
代码1

    def merge(self, intervals):
        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

思路2
同思路1首先对原数组进行排序，然后遍历整个数组，如果前一个元素是空值，则继续向前，如果能和前一个元素合并，则用合并结果替换前一个元素，将当前元素置空，遍历结束后只需取出数组非空部分。
代码2

    def merge(self, intervals):
        if len(intervals) < 2:
            return intervals
        intervals = sorted(intervals, key=lambda x: x.start)
        i = 1
        while i < len(intervals):
            k = i - 1
            while intervals[k] is None:
                k -= 1
            if intervals[i].start <= intervals[k].end:
                intervals[k] = Interval(intervals[k].start,
                                        intervals[k].end if intervals[k].end >= intervals[i].end else intervals[i].end)
                intervals[i] = None
            i += 1
        return filter(lambda x: x is not None, intervals)

思路3
不对数组进行排序，直接遍历并将向前逐个合并，若能合并则记录下标及合并值，到达数组开始位置跳出循环，并将记录下标位置设置为合并值，最终将数组去空后排序。
代码3

    def combin(self, a, b):
        return Interval(a.start if a.start < b.start else b.start, a.end if a.end > b.end else b.end)
    def judge(self,a,b):
        if a.start < b.start:
            return a.end >= b.start
        else:
            return b.end >= a.start
    def merge(self, intervals):
        if len(intervals) < 2:
            return intervals
        i = 1
        while i < len(intervals):# 向后遍历
            j = i#标志位
            tmp = intervals[j] #缓存合并区间
            intervals[j] = None
            k = j - 1
            while k >= 0:# 向前遍历
                if intervals[k] is None:
                    k -= 1
                    continue
                if self.judge(tmp,intervals[k]):# 判断能否合并
                    tmp = self.combin(intervals[k], tmp) #更新缓存
                    intervals[k] = None # 置空
                    j = k #更新标志位
                k -= 1
            intervals[j] = tmp
            i += 1
        return sorted(filter(lambda x: x is not None, intervals),key=lambda x: x.start)

结语
感觉只用思路3是符合挑战要求的，但提交的时候竟然超时了23333