https://leetcode.com/problems/interval-list-intersections/
本题用双指针。(想了下,也可以用线段树,和天际线那道题类似)
class Solution {
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
int i = 0;
int j = 0;
List<int[]> list = new ArrayList<>();
while (i < firstList.length || j < secondList.length) {
if (i == firstList.length) {
j++;
} else if (j == secondList.length) {
i++;
} else {
// 有重叠情况:
// [ ]
// [ ]
// [ ]
// [ ]
// [ ]
// [ ]
// [ ]
// [ ]
// 无重叠情况:
// [ ]
// [ ]
// [ ]
// [ ]
int start = Math.max(firstList[i][0], secondList[j][0]);
int end = Math.min(firstList[i][1], secondList[j][1]);
if (start <= end) {
list.add(new int[]{start, end});
if (firstList[i][1] < secondList[j][1]) {
i++;
} else {
j++;
}
} else {
if (firstList[i][1] < secondList[j][0]) {
i++;
} else {
j++;
}
}
}
}
int[][] result = new int[list.size()][];
for (int k = 0; k < list.size(); k++) {
result[k] = list.get(k);
}
return result;
}
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/sinat_42483341/article/details/121507466
内容来源于网络,如有侵权,请联系作者删除!