来源Leetcode第57题插入区间
给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 1:
输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
输出: [[1,5],[6,9]]
排序
同合并区间，就是要注意当intervals为空时，可以直接返回newInterval
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
| public int[][] insert(int[][] intervals, int[] newInterval) {
List<int []> ans = new ArrayList<>();
if(intervals == null || intervals.length == 0)
{
ans.add(newInterval);
return ans.toArray(new int[0][]);
}
int [][] matrix = new int[intervals.length + 1][2] ;
System.arraycopy(intervals,0,matrix,0,intervals.length);
matrix[intervals.length] = newInterval;
Arrays.sort(matrix, new Comparator<int[]>() {
@Override
public int compare(int[] ints, int[] t1) {
return ints[0] - t1[0] ;
}
});
int i = 0 ;
while(i < matrix.length){
int left = matrix[i][0];
int right = matrix[i][1];
while(i < matrix.length && right>= matrix[i][0]){
right = Math.max(right,matrix[i][1]);
i++;
}
ans.add(new int[] {left,right});
}
return ans.toArray(new int [0][]);
}
|
插入后合并
注意到初始数组是无重叠的 ，按照区间起始端点排序的，因而可以先找到要插入的地方，然后前后合并即可。
具体思路见注释。
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| class Solution {
public int midSearch(int[][] intervals, int[] newInterval){
int start = 0;
int end = intervals.length;
int mid;
while (start<end){
mid = (start+end)/2;
if(intervals[mid][0]<newInterval[0])
start = mid+1;
else
end = mid;
}
return start;
}
public int[][] insert(int[][] intervals, int[] newInterval) {
int count = 0;
int[] buffer = new int[2];
buffer[0] = newInterval[0];
buffer[1] = newInterval[1];
int place = midSearch(intervals,newInterval);
int temp;
for(temp = place;temp<intervals.length;temp++){
if(buffer[1]<intervals[temp][0])
break;
}
if(temp!=place){
buffer[1] = Math.max(intervals[temp-1][1],buffer[1]);
count += temp - place;
}
if (place!=0){
if(intervals[place-1][1]>=buffer[0]){
buffer[0] = intervals[place-1][0];
buffer[1] = Math.max(intervals[place-1][1],buffer[1]);
place--;
count++;
}
}
int target;
int[][] result = new int[intervals.length - count + 1][2];
for(target = 0;target<place;target++){
result[target][0] = intervals[target][0];
result[target][1] = intervals[target][1];
}
result[target][0] = buffer[0];
result[target][1] = buffer[1];
target++;
for(;temp<intervals.length;temp++,target++){
result[target][0] = intervals[temp][0];
result[target][1] = intervals[temp][1];
}
return result;
}
}
|
常规思考
来自题解
先考虑三种极端情况：
- intervals为空
- newInterval[1] < intervals[0][0],直接插入第一个位置
- newInterval[0] > intervals[-1][1],直接插入最后一个位置
下面就要考虑重叠情况了
我们目标就是找到和newInterval相关那几个区间.
首先,左边,当newInterval[0] > intervals[i][1]说明没有和该区间没有重叠部分,继续遍历下一个区间,比如intervals = [[1,3],[6,9]], newInterval = [2,5]
然后,再看右边,这里有个情况,就是 当intervals[i][0] > newInterval[1]说明newInterval没有和任何区间重合,比如intervals = [[1,3],[6,9]], newInterval = [4,5],直接插入即可.
接下来我们要找右边重合区域,当while i < n and newInterval[1] >= intervals[i][0]说明有重叠部分,记录左边最大值!
最后把数组拼接一下即可!
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> res = new ArrayList<>();
int i = 0;
while (i < intervals.length && newInterval[0] > intervals[i][1]) {
res.add(intervals[i]);
i++;
}
int[] tmp = new int[]{newInterval[0], newInterval[1]};
while (i < intervals.length && newInterval[1] >= intervals[i][0]) {
tmp[0] = Math.min(tmp[0], intervals[i][0]);
tmp[1] = Math.max(tmp[1], intervals[i][1]);
i++;
}
res.add(tmp);
while (i < intervals.length) {
res.add(intervals[i]);
i++;
}
return res.toArray(new int[0][]);
}
}
|