Source: InterviewBit

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

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Given intervals [1,3],[6,9] insert and merge [2,5] would result in [1,5],[6,9].

Example 2:

Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] would result in [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Make sure the returned intervals are also sorted.

給定數個不重疊的數字區間，並在這些數字區間裡面插入另一個區間並對重疊部分進行合併後輸出更新之不重疊數字區間。

解題：

  1. 以釋例2做分析，先將欲插入合併之區間左端進行判斷：如左端在兩個不重疊區間之間＝＞插入一個新的區間並以該值作為區間左端；如左端被包含在某個區間之內＝＞不做任何變更，進入右端值檢視；
  2. 對右端值則視其超過哪些區間之左端及右端值，並將超過部分取代或消除（同時超過左端及右端）；
  3. 可將輸出的陣列分為三個部分：所有原區間右端值小於插入區間左端值者（不受影響）、插入合併執行完成之區間、所有原區間左端值大於插入區間右端值者（不受影響）。

Code:


class Solution:
    # @param intervals, a list of Intervals
    # @param newInterval, a Interval
    # @return a list of Interval
    def insert(self, intervals, newInterval):
        start, end = newInterval.start, newInterval.end
        if len(intervals) == 0: return [newInterval]
        elif start >= intervals[-1].end: return intervals[:] + [newInterval]
        left, right = 0,0
        while right < len(intervals):
            if end  intervals[right].end: left += 1
            else:
                start = min(start, intervals[right].start)
                end = max(end, intervals[right].end)
            right += 1
        return intervals[:left] + [Interval(start, end)] + intervals[right:]

在整理的時候發現之前在網站上面寫的答案真是又臭又長，長到我自己都不想花時間看……XD

GitHub: GitHub

發表留言