LeetCode 57 插入区间

给你一个 无重叠的 ,按照区间起始端点排序的区间列表。

在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。

示例 1:

输入:intervals = [[1,3],[6,9]], newInterval = [2,5]
输出:[[1,5],[6,9]]

示例 2:

输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出:[[1,2],[3,10],[12,16]]
解释:这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

示例 3:

输入:intervals = [], newInterval = [5,7]
输出:[[5,7]]

示例 4:

输入:intervals = [[1,5]], newInterval = [2,3]
输出:[[1,5]]

示例 5:

输入:intervals = [[1,5]], newInterval = [2,7]
输出:[[1,7]]

提示:

  • 0 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= intervals[i][0] <= intervals[i][1] <= 105
  • intervals 根据 intervals[i][0] 按 升序 排列
  • newInterval.length == 2
  • 0 <= newInterval[0] <= newInterval[1] <= 105

解题:

func insert(intervals [][]int, newInterval []int) [][]int {
	if len(intervals) == 0 {
		return [][]int{newInterval}
	}
	var r [][]int
	flag := true
	for _, v := range intervals {
		if flag && newInterval[1] < v[0] {
			r = append(r, newInterval)
			r = append(r, v)
			flag = false
			continue
		}
		if flag && newInterval[0] <= v[1] {
			if newInterval[1] > v[1] {
				v[1] = newInterval[1]
			}
			if newInterval[0] < v[0] {
				v[0] = newInterval[0]
			}
			r = append(r, v)
			flag = false
			continue
		}
		l := len(r)
		if newInterval[0] > v[1] || v[0] > r[l-1][1] {
			r = append(r, v)
			continue
		}
		if v[0] > r[l-1][0] && v[0] <= r[l-1][1] && v[1] > r[l-1][1] {
			r[l-1][1] = v[1]
		}
	}
	if newInterval[0] > intervals[len(intervals)-1][1] {
		r = append(r, newInterval)
	}
	return r
}

官方解答:

1.模拟

func insert(intervals [][]int, newInterval []int) (ans [][]int) {
	left, right := newInterval[0], newInterval[1]
	merged := false
	for _, interval := range intervals {
		if interval[0] > right {
			// 在插入区间的右侧且无交集
			if !merged {
				ans = append(ans, []int{left, right})
				merged = true
			}
			ans = append(ans, interval)
		} else if interval[1] < left {
			// 在插入区间的左侧且无交集
			ans = append(ans, interval)
		} else {
			// 与插入区间有交集,计算他们的并集
			left = min(left, interval[0])
			right = max(right, interval[1])
		}
	}
	if !merged {
		ans = append(ans, []int{left, right})
	}
	return
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

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

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注