LC56.合并区间

1. 题目

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

示例 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] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 10⁴
• intervals[i].length == 2
• 0 <= startᵢ <= endᵢ <= 10⁴

2. 思路

• 第一步，按照区间的左端点进行升序排序，如果左端点相同，按照右端点的数值进行升序排序。

sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] == intervals[j][0] {
			return intervals[i][1] < intervals[j][1]
		} else {
			return intervals[i][0] < intervals[j][0]
		}
	})

• 第二步，判断区间是否有重叠情况，也就是新区间的左端点 < 旧区间的右断点。如果存在重叠的情况，那么更新整体区间的右端点为 max(旧区间的右端点，新区间的右端点) 。不过不存在重叠的情况，那么将上一个区间 推入答案当中。
• 第三步，对于区间数组当中的最后一个元素，无论是否需要合并，都没有将其推入答案当中，因此，需要执行一次 ans = append(ans, []int {startPoint, endPoint})

---

• 对于区间问题，需要了解一些常识

2 个区间的关系有以下 6 种，但是其实可以变成上面 3 种情况（只需要假设 第一个区间的起始位置 <= 第二个区间的起始位置，如果不满足这个假设，交换这两个区间）。这 3 种情况的合并的逻辑都很好写。 作者：Sweetiee 🍬 链接：https://leetcode.cn/problems/merge-intervals/solutions/204805/chi-jing-ran-yi-yan-miao-dong-by-sweetiee/

3. 代码

// Created by Albert at 2023/09/12 16:23
// leetgo: 1.3.7
// https://leetcode.cn/problems/merge-intervals/

package main

import (
	// "bufio"
	"fmt"
	// "os"
	"sort"

	. "github.com/j178/leetgo/testutils/go"
)

// @lc code=begin

func merge(intervals [][]int) (ans [][]int) {
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] == intervals[j][0] {
			return intervals[i][1] < intervals[j][1]
		} else {
			return intervals[i][0] < intervals[j][0]
		}
	})

	startPoint := intervals[0][0]
	endPoint := intervals[0][1]

	for i := 1; i < len(intervals); i++ {
		if intervals[i][0] <= endPoint {
			if intervals[i][1] > endPoint {
				endPoint = intervals[i][1]
			}
		} else {
			ans = append(ans, []int{startPoint, endPoint})
			startPoint = intervals[i][0]
			endPoint = intervals[i][1]
		}
	}

	ans = append(ans, []int{startPoint, endPoint})

	return
}

// @lc code=end

func main() {
	// stdin := bufio.NewReader(os.Stdin)
	// intervals := Deserialize[[][]int](ReadLine(stdin))

	intervals := [][]int{
		{1, 3},
		{2, 6},
		{8, 10},
		{15, 18},
	}
	ans := merge(intervals)

	fmt.Println("\noutput:", Serialize(ans))
}