GuilinDev
Lc0057
05 August 2008
57 Insert Interval
原题
给出一个_无重叠的 ，_按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
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].
Example 3:
1
2
Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
Example 4:
1
2
Input: intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]
Example 5:
1
2
Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]
分析
- 时间复杂度：O(N)。我们只遍历了一次输入元素。
- 空间复杂度：O(N)，输出答案所使用的空间。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
// 0. Notice intervals is already sorted in ascending order，已排序过
List<int[]> mergedIntervals = new ArrayList<>();
int i = 0, len = intervals.length; // 虽然有3个while循环，但是i从左到右只会访问每个元素一次
// 1. merge intervals that come before new interval
// |--------------|
// |---| newInterval
while (i < len && intervals[i][1] < newInterval[0]) {
mergedIntervals.add(intervals[i]);
i++;
}
// 2. Merge overlapping intervals with new intervals
// |--------------|
// |---| newInterval
while (i < len && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
i++;
}
// 3. Add the merged new interval
// |----------------|
// |--------| mergedInterval
mergedIntervals.add(newInterval);
// 4. Add all the remaining intervals after the new interval
// |--------------|
// |----------------|
while (i < len) {
mergedIntervals.add(intervals[i]);
i++;
}
return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
}
}