磊磊落落的博客

关注技术前沿 · 记录内心波澜 · 分享读书感想

  • 计算机
  • 随笔
  • 读书
  • 观影
  • 练字

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 入室抢劫者

文章归档

标签

Golang (96) Python (2) Ruby (1) 工具使用 (3) 数据分析 (1) 机器学习 (1) 算法 (66) 练字 (1) 观影 (2) 读书 (6) 随笔 (48)

请我喝杯茶

若我的文章对您有帮助,欢迎小额打赏,以支持我更好的写作!

微信 支付宝

友情链接

LeetCode题目Golang实现汇总
Go语言中文网
Tony Bai
...
本站文章采用知识共享署名4.0许可证进行许可

Powered by WordPress | Copyright leileiluoluo.com©2017-2019 | 晋ICP备08100400号-4 | 关于本站 | 友情链接 |