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实现代码

https://github.com/leileiluoluo/

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
}

LeetCode 56 合并区间

相关文章

评论