Insert Interval

Posted on | Edited on | In | | Views:

Insert Interval

Given a set of non-overlapping intervlas, insert a new interval into intervals(merge if necessary)

给一个组特殊的数据结构interval和一个目标interval, 每个interval有start和end. 输入的一组interval没有重合, 要求把新的interval插入到原来的那一组interval当中, 如果有需要合并的话, 对interval进行合并

例如:
输入是 [[1, 3], [6, 9]] 和 [2, 5], 那么我们需要返回[[1, 5], [6, 9]]

思路

首先可以明确的是, 要插入一个新的interval, 有下面五种可能

  1. 跟原来的没有任何重叠, 不需要合并
  2. start落在其中一个interval当中, 但是end不在任何interval当中, 需要改变原来interval的end值
    • [[1, 3], [6, 9]] 和 [2, 5]. 这里需要把[1, 3]扩大成[1, 5]
  3. end落在其中一个interval当中, 但是start不再任何interval当中, 需要改变原来interval的start值
    • [[2, 5], [6, 9]] 和 [1, 4]. 这里需要把[2, 5]扩大成[1, 5]
  4. start落在其中一个interval当中, end落在另外一个interval当中, 需要把多个interval进行合并.
    • [[1, 3], [6, 9]] 和 [2, 7]. 这里需要把[1, 3], [6, 9]合并, 变成 [1, 6]
  5. start和end都落在同一个interval当中, 那么什么也不用改.

清楚了上面的规则之后, 我们可以把工作简化成合并interval. 因为作为输入的一组interval是经过排序的, 把newInterval插入后也按照interval的start值进行排序. 比如说, [[1, 3], [6, 9]], 插入[2, 4]之后, 变成[[1, 3], [2, 4], [6, 9]]. 然后我们对这一组interval按照上面说的规则进行合并, 就是我们最终的答案.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def merge(interval):
    i = 1
    while i < len(intervals):
        prev = intervals[i-1]
        cur = intervals[i]
        if cur.start <= prev.end:
            if cur.end > prev.end:
                prev.end = cur.end
                intervals.pop(i)
            else:
                intervals.pop(i)
        else:
            i += 1
    return intervals

def insert(intervals, newInterval):
    intervals.append(newInterval)
    intervals.sort(key=lambda x:x.start)
    return merge(intervals)

复杂度

因为要进行排序, 所以bets case: $O(n)$, average case: $O(nlogn)$, worst case: $O(nlogn)$.

EOF