Merge Intervals

合并或者插入区间的这类题个人感觉最优的做法是比较像贪心算法，但是因为输入数据的特点太像扫描线了，所以这里自己用了一种扫描线算法强行套到这个题上面去了，所以时间复杂度变为O(nlgn)，空间复杂度则为O(n)，并且是用了O(4n)的额外空间，不是一个很好的解，但是也表明此题能用扫描线解，下面是代码

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

def comparator(A, B):
    if A[1] == B[1]:
        return A[0] - B[0]
    if A[0] == B[0]:
        return -1 if A[1] else 1
    return A[0] - B[0]

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        tmp = []
        start = []                # 这里还需要start和end两个额外单独记录起点和终点的数组
        end = []
        for interval in intervals:
            tmp.append([interval.start, 1])
            tmp.append([interval.end, 0])
            start.append(interval.start)
            end.append(interval.end)

        tmp.sort(cmp = comparator)
        start.sort()
        end.sort()
        intervals.sort(cmp = lambda x,y:x.start - y.start)

        res = []
        count = 0
        base, step = 0, 0
        for intv in tmp:
            if intv[1]:
                count += 1
                step += 1
            else:
                count -= 1
                if count == 0:
                    res.append(Interval(start[base], end[base + step - 1]))        # 这一行是很关键的
                    base += step
                    step = 0

        return res

这道题还可以对每一个区间进行类似贪心的检查，即当栈顶的区间和当前遍历的区间有重合时，我们把两个区间合并再放入栈顶，如果没有重合则把当前区间放入栈顶，这样就能得到merge过后的结果了

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        res = []
        for interval in sorted(intervals, cmp=lambda x, y : cmp(x.start, y.start)):
            if res and res[-1].end >= interval.start:
                res[-1] = Interval(res[-1].start, max(res[-1].end, interval.end))        # 你不知道当前区间是不是比栈顶区间还要大
            else:
                res.append(interval)
        return res

Insert Interval

这题如果直接套merge的第二种解法是可行的，因为本身数组有序，实际上排序的时间复杂度就被减小了，但是应该还有遍历一遍就能搞定的做法，以后再研究

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """

        intervals.append(newInterval)
        res = []
        for interval in sorted(intervals, cmp = lambda x, y: cmp(x.start, y.start)):
            if res and res[-1].end >= interval.start:
                res[-1] = Interval(res[-1].start, max(res[-1].end, interval.end))
            else:
                res.append(interval)
        return res

O(n)的做法，毛子哥带你用Python系列...列表可以不用调append函数直接加数进去，只要加个逗号就行了

算法上以newInterval的start和end为中间点，合并一切可以并在一起的interval到这两个变量里面去，其余的或左或右最终相加就可以了

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, right = [], []
        for interval in intervals:
            if interval.end < start:
                left += interval,
            elif interval.start > end:
                right += interval,
            else:
                start = min(start, interval.start)
                end = max(end, interval.end)
        return left + [Interval(start, end)] + right