Description
Insert Interval
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:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
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:]...)...)
}
|
Similar Problem
