56.M 合并区间

Problem: 56. 合并区间

思路

先把区间按照左边界进行排序，排序后有重叠的区间必定是相邻的。

遍历排序后的区间，先把第一个区间加入结果中，然后遍历后续区间：

• 如果遍历到的区间跟结果中的最后一个区间有重叠，而且当前区间的右边界大于结果中最后一个区间的右边界，则把结果中最后一个区间的右边界更改为当前区间的右边界。

• 否则，把当前区间加入结果。

Code

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

	var ans [][]int
	ans = append(ans, intervals[0])

	for i := 1; i < len(intervals); i++ {
		left := intervals[i][0]
		right := intervals[i][1]
		lastRight := ans[len(ans)-1][1]
		if left <= lastRight {
			if right > lastRight {
				ans[len(ans)-1][1] = right
			}
		} else {
			ans = append(ans, intervals[i])
		}
	}

	return ans
}