【中等】56. 合并区间

2023-12-20 07:47:49

题目

56. 合并区间

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:
输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。

用例3
intervals =[[1,4],[0,1]]
输出
[[0,1]]

提示:
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

解题

题目没提、示例没举,所以没考虑逆序情况。实际真得考虑的。
还在用冒泡,嘤嘤嘤。
看了题解:自己的解法真原始且幼稚

func merge(intervals [][]int) [][]int {

    result := [][]int{}
    s := make([]int, 2)

    for i:=0 ; i < len(intervals); i++{
        for j:=i+1 ; j < len(intervals); j++{
            if intervals[i][0] > intervals[j][0]{
                intervals[i], intervals[j] = intervals[j], intervals[i]
            }
        }
    }

    s = intervals[0]
    for _, v := range intervals{
        if v[0]<=s[1]{
            if v[0]<s[0]{
                s[0] = v[0]
            }
            if v[1] > s[1]{
                s[1] = v[1]
            }
        } else {
            result = append(result, s)
            s = v
        }
    }
    result = append(result, s)

    return result
}

题解

方法一:

1

func merge(intervals [][]int) (ans [][]int) {
	sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
	ans = append(ans, intervals[0])
	for _, e := range intervals[1:] {
		if ans[len(ans)-1][1] < e[0] {
			ans = append(ans, e)
		} else {
			ans[len(ans)-1][1] = max(ans[len(ans)-1][1], e[1])
		}
	}
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

作者:ylb
链接:https://leetcode.cn/problems/merge-intervals/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

时间:O(nlogn)
空间:O(logn)

长进

  1. 排序都得顺一遍
  2. 最新版本go中 新增了max方法

文章来源:https://blog.csdn.net/Miller_6/article/details/135046798
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。