给出一个区间的集合，请合并所有重叠的区间。
- 示例 1:
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. - 示例 2:
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。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
28object MergeRange {
def main(args: Array[String]): Unit = {
merge(Array(Array(1, 2), Array(3, 5), Array(4, 8))).foreach(a => println(a(0), a(1)))
merge(Array(Array(1, 4), Array(2, 3))).foreach(a => println(a(0), a(1)))
merge(Array(Array(1, 3), Array(8, 10), Array(2, 6), Array(10, 18))).foreach(a => println(a(0), a(1)))
}
def merge(intervals: Array[Array[Int]]): Array[Array[Int]] = {
val sorted = intervals.sortWith(_ (0) < _ (0))
val res = new ListBuffer[Array[Int]]()
var i = 0
var j = 1
while (j < sorted.length) {
if (sorted(i)(1) >= sorted(j)(0)) {
sorted(i)(1) = Math.max(sorted(i)(1), sorted(j)(1))
j += 1
} else {
res += sorted(i)
i = j
j += 1
}
}
res += sorted(i)
res.toArray
}
}