⚔ LeetCode | 57. Insert Interval

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

Problem

LeetCode 57. Insert Interval

Difficulty : Hard

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

1
2
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

1
2
3
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Analysis

这道题虽然是一道Hard题，但是看上去还是属于比较简单的题目，将一个新的区间合并到原有的区间当中。

Approach 1

最基本的方法就是依次遍历整个区间数组，判断是否和新的区间有交集，没有就直接放入新的数组里面，如果有在具体处理。

其基本的步骤如下：

  • 首先，找出所有在新的区间之前的区间，放入新的数组中
  • 然后，在与新区间有交集的原区间中，找出其最小的Start以及最大的End，然后构成一个新的区间加入到结果中
  • 最后，将剩余的区间也放入结果中

我们来看一个例子

原区间：[[1,2], [3,5], [6,7], [8,10], [12,16]]新的区间： [4, 8]

我们可以将原区间分为三个部分[1,2]、[3,5],[6,7],[8,10]和[12,16]

第一个和第三个部分和新的区间并没有交集，因此可以直接放入结果当中

然后第二个部分和新的区间融合，找出其最小的Start和最大的End，构成新的区间[3,10]

最后结果就是[1,2],[3,10],[12,16]

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func insert(intervals []Interval, newInterval Interval) []Interval {
	var res []Interval
	var i int
	for i < len(intervals) && intervals[i].End < newInterval.Start {
		i++
	}
	res = append(res, intervals[:i]...)
	for i < len(intervals) && intervals[i].Start <= newInterval.End {
		if intervals[i].Start  < newInterval.Start {
			newInterval.Start = intervals[i].Start
		}
		if intervals[i].End > newInterval.End {
			newInterval.End = intervals[i].End
		}
		i++
	}
	res = append(res, newInterval)
	res = append(res, intervals[i:]...)
	return res
}

这个算法只需要遍历原区间数组一次，因此时间复杂度为O(n)，空间复杂度为O(n)

Summary

这道题的的确比较简单，只需要明确合并区间的条件，根据边界判断一下就可以得到答案。

土豪通道
0%