LeetCode 56 合并区间
2019年7月24日
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]重叠。
题目出处:
https://leetcode.com/problems/merge-intervals/
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实现代码
https://github.com/olzhy/leetcode/blob/master/56_Merge_Intervals/test.go
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 }Golang , 算法
上一篇: LeetCode 34 在有序数组寻找元素的出现范围
下一篇: LeetCode 198 入室抢劫者
文章归档
请我喝杯茶
微信 | 支付宝 | |
![]() |
![]() |