-
Difficulty: Medium
-
Related Topics: Array, Sort
Description
Given an array of intervals
where intervals[i] = [starti, endi]
, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
给定一组区间 intervals
(intervals[i] = [starti, endi]
),合并所有重叠的区间,并返回一个没有重叠的区间,这个区间能正好覆盖输入的区间。
Examples
Example 1
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
Solution
首先,有序的区间方便于合并,所以第一步自然是给区间排序。然后取出第一个区间并遍历剩余区间:
-
如果 end 大于等于遍历到的区间的 start,更新 end;
-
否则,将这个区间加入结果集,更新当前的区间。
代码如下:
import kotlin.math.max
class Solution {
fun merge(intervals: Array<IntArray>): Array<IntArray> {
intervals.sortWith(Comparator { i1, i2 ->
if (i1[0] != i2[0]) {
compareValues(i1[0], i2[0])
} else {
compareValues(i1[1], i2[1])
}
})
if (intervals.isEmpty()) {
return arrayOf()
}
val result = arrayListOf<IntArray>()
var (start, end) = intervals[0]
for (i in 1..intervals.lastIndex) {
if (end >= intervals[i][0]) {
end = max(end, intervals[i][1])
} else {
result.add(intArrayOf(start, end))
start = intervals[i][0]
end = intervals[i][1]
}
}
result.add(intArrayOf(start, end))
return result.toTypedArray()
}
}