57. 插入区间 [hard]

https://leetcode-cn.com/problems/insert-interval/

给出一个无重叠的，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1:

输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
输出: [[1,5],[6,9]]

示例 2:

输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出: [[1,2],[3,10],[12,16]]
解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

通过次数24,953 | 提交次数66,821

First Try

2020-07-04

按这个写法来说，根本不算hard题目啊，算easy都可以。考虑到边界条件较多，可以算是median题目吧。

对newinterval进行不断汇总，在循环中考虑是否添加合并就可以了，算是一种迭代的思路吧。

class Solution(object):

    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        # 按顺序来处理，用merge的方式，思路清晰了许多
        if not len(intervals):
            return [newInterval]
        seq = []
        for pre in intervals:
            if not newInterval:
                seq.append(pre)
                continue

            # 三种情况考虑下，比pre小，比pre大，与pre交叉
            if pre[0] > newInterval[1]:
                seq.append(newInterval)
                seq.append(pre)
                newInterval = False
            elif pre[1] < newInterval[0]:
                seq.append(pre)
                continue
            else:
                # 把这个元素当成新的插入元素，同时不放回之前的pre    
                # 不过如果这已经是最后一个元素了，反而差点被遗漏了
                pre = [min(pre[0], newInterval[0]), max(pre[1], newInterval[1])]
                # print('vola',)
                newInterval = pre
        # 差点被遗漏
        if newInterval:
            seq.append(newInterval)
        return seq

执行用时：28 ms, 在所有 Python 提交中击败了71.66%的用户
内存消耗：14.3 MB, 在所有 Python 提交中击败了100.00%的用户

failed try

打算按照for range的写法一路平推下去，出现的错误情况太多了，最后都写绕了。所以如果一开始的思路不对，再简单的题目都可能写出死胡同来。

# tmd的，一路平推太多错误了。。。 
class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        # 有个情况忘了考虑了: [[1,5]] [6,8]
        # tmd又有错误 [[1, 5]] [2, 3]
        if not len(intervals):
            return [newInterval]
        seq = []
        flag = False
        for i in range(0, len(intervals)):
            if flag:
                break
            ele = intervals[i]
            # print("vola", ele, intervals)
            if ele[1] < newInterval[0]:
                seq.append(ele)
            if ele[0] > newInterval[1]:
                seq.append(newInterval)
                seq.append(ele)
                flag = True
            elif ele[1] >= newInterval[0]:
                ele = [min(ele[0], newInterval[0]), max(ele[1],newInterval[1])]
                # print("ele", ele)
                for j in range(i + 1, len(intervals)):
                    if flag:
                        seq.append(intervals[j])
                    elif ele[1] >= intervals[j][0]:
                        ele = [ele[0], max(ele[1], intervals[j][1])]  # interval继续扩展吞并中, 但如果吞并到最后需要考虑别遗忘了
                    elif ele[0] < intervals[j][0]:
                        seq.append(ele)
                        seq.append(intervals[j])
                        flag = True # interval处理完毕
                if not flag:
                    seq.append(ele)
                    flag = True  # 不管如何，总归是有处理了
        if not flag:
            seq.append(newInterval)
        return seq

57. 插入区间 [hard]​

First Try​

57. 插入区间 [hard]

First Try