原题地址：https://leetcode.cn/problems/interval-list-intersections/
题解
每次用area1和area2两个指针维护当前区间，若area1和area2有交集，则有
- 交集左边界必然是area1和area2中较大的左边界
- 交集右边界必然是area1和area2中较小的右边界
故用left和right保存下两个值
- 当left<=right时，area1和area2存在交集，将left和right存入temp数组并存入list中
- 不论两个区间是否存在交集，此时都需要推进迭代，area1和area2中必然是右边界较大的那个区间需要保留，则右边界较小的区间被舍弃，指针++
时间复杂度：O(M+N)
空间复杂度：O(M+N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
List<int[]> list=new ArrayList<>();
int[] temp;
int area1=0,area2=0,left,right;
while(area1<firstList.length&&area2<secondList.length){
temp=new int[2];
left=Math.max(firstList[area1][0],secondList[area2][0]);
right=Math.min(firstList[area1][1],secondList[area2][1]);
if(right>=left){
temp[0]=left;
temp[1]=right;
list.add(temp);
}
if(firstList[area1][1]>secondList[area2][1])area2++;
else area1++;
}
return list.toArray(new int[list.size()][]);
}
}
|
