LeetCode 57. Insert Interval

Description

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:
1
2
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
1
2
3
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

在给出的有序区间中插入新的区间，需要合并相邻的区间。

Solution

先找出所有比新区间小的区间
再找出所有比新区间大的区间
在查找过程中将新区间与相邻区间合并
最后返回[小区间]+[新区间]+[大区间]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func insert(intervals []Interval, newInterval Interval) []Interval {
    length := len(intervals)
    if length == 0 {
        return []Interval{newInterval}
    }

    // 分割比 newInterval 小的区间
    lEnd := 0
    for lEnd < length && newInterval.Start > intervals[lEnd].End {
        lEnd++
    }

    // 边界判断
    if lEnd == length {
        return append(intervals, newInterval)
    }

    if intervals[lEnd].Start < newInterval.Start {
        // 将当前区间与 newInterval 合并
        newInterval.Start = intervals[lEnd].Start
    }

    // 分割比 newInterval 大的区间
    rStart := lEnd
    for rStart < length && newInterval.End >= intervals[rStart].Start {
        if intervals[rStart].End > newInterval.End {
            // 将当前区间与 newInterval 合并
            newInterval.End = intervals[rStart].End
        }
        rStart++
    }

    // append 时用 newInterval 建立新的 Slice 与 intervals[rStart:] 合并
    // 再与 intervals[:lEnd] 合并
    // 之前直接将 newInterval append 到 intervals[:lEnd] 后面，再与 intervals[rStart:] 合并
    // 会导致 intervals[rStart:] 的内存区域被覆盖
    return append(intervals[:lEnd], append([]Interval{newInterval}, intervals[rStart:]...)...)
}

LeetCode 57. Insert Interval

LeetCode 57. Insert Interval - Answer LeetCode编程练习解答

Description

Solution

Similar Problem