给出一个无重叠的 ，按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
- 示例 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] 重叠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
39
40
41
42
43
44
45
46
47
48
49
50
51object RangeInsert {
def main(args: Array[String]): Unit = {
insert(Array(Array(1, 3), Array(6, 9)), Array(2, 5)).foreach(a => println(a(0), a(1)))
insert(Array(Array(1, 2), Array(3, 5), Array(6, 7), Array(8, 10), Array(12, 16)), Array(4, 8)).foreach(a => println(a(0), a(1)))
}
def insert(intervals: Array[Array[Int]], newInterval: Array[Int]): Array[Array[Int]] = {
val list = new ListBuffer[Array[Int]]()
var added = false
for (i <- 0 until intervals.length) {
if (intervals(i)(0) >= newInterval(0) && !added) {
added = true
list += newInterval
}
if (i + 1 < intervals.length && intervals(i)(0) < newInterval(0) && newInterval(0) <= intervals(i + 1)(0)) {
added = true
list += intervals(i)
list += newInterval
} else {
list += intervals(i)
}
}
if (!added) {
list += newInterval
}
merge(list.toArray)
}
def merge(intervals: Array[Array[Int]]): Array[Array[Int]] = {
val res = new ListBuffer[Array[Int]]()
var i = 0
var j = 1
while (j < intervals.length) {
if (intervals(i)(1) >= intervals(j)(0)) {
intervals(i)(1) = Math.max(intervals(i)(1), intervals(j)(1))
j += 1
} else {
res += intervals(i)
i = j
j += 1
}
}
res += intervals(i)
res.toArray
}
}