LeetCode 56 合并区间
1 题目描述
给定一组区间，合并所有重叠的区间。
例子1：
输入：
[[1,3],[2,6],[8,10],[15,18]]
输出：
[[1,6],[8,10],[15,18]]
释义：
[1,3]与[2,6]重叠，合并为[1,6]
例子2：
输入：
[[1,4],[4,5]]
输出：
[[1,5]]
释义：
[1,4]与[4,5]重叠
题目出处：LeetCode
2 解决思路
对于两个坐标x[0,1]与y[0,1]，若最小的右边界大于等于最大的左边界则说明重叠，即若min(x[1], y[1]) >= max(x[0], y[0])，则重叠。
整体的比较步骤为：
a）第1个区间与其后2…n个区间比较，合并重叠的部分，并更新到第1个区间；
b）第2个区间与其后3…n个区间比较，合并重叠的部分，并更新到第2个区间；
…
i）第i个区间与其后i+1…n个区间比较，合并重叠的部分，并更新到第i个区间；
…
一般地，若在i）步没有找到合并的部分，则进入i+1步，否则重复i）步。 这样，遍历到最后即完成合并。
3 Golang实现代码
func min(x, y int) int {
if x < y {
return x
}
return y
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
func merge(intervals [][]int) [][]int {
i, j := 0, 0
for i < len(intervals) {
merged := false
for j = i + 1; j < len(intervals); {
x, y := intervals[i], intervals[j]
if min(x[1], y[1]) >= max(x[0], y[0]) {
merged = true
// fix intervals[i]
intervals[i][0], intervals[i][1] = min(x[0], y[0]), max(x[1], y[1])
// remove intervals[j]
intervals[j] = intervals[len(intervals)-1]
intervals = intervals[:len(intervals)-1]
continue
}
j++
}
if merged {
continue
}
i++
}
return intervals
}
| 微信 | 支付宝 | |||
 |
 |