问题分析
有的时候,会遇到给定一系列的区间,求交集or并集,或者合并的题.
这些题的解题方式比较通用个,做一个总结.
会用到集合和归并排序的相关知识.
两个区间的关系有六种,如果我们首先对区间按照区间左边界进行排序,那么就会编程3中关系:
A 包含 B ==> A[0] <= B[0] && A[1] >= B[1]
A 交集于 B ==> A[0] <= B[0] || A[1] >= B[1]
A 无交集 B ==> A[1] < B[0]
解题套路
算法的题解法是:
首先对 区间集合进行排序.
将这些集合分为已归并 + 未归并
从已归并中取出最后一个 + 未归并的第一个进行计算:
根据以上的三种关系来处理已归并集合的最后一个区间:
A 包含 B ==> A[0] <= B[0] && A[1] >= B[1] ==> 未归并 自动归并到已归并集合,不用处理
A 交集于 B ==> A[0] <= B[0] || A[1] >= B[1] ==> 修改 已归并最后一个区间的右区间 为B[1]
A 无交集 B ==> A[1] < B[0] ==> 将B 区间添加到已归并区间中
示例
56. 合并区间
题解
class Solution {
public int[][] merge(int[][] intervals) {
/**
* 首先做一个排序.按照做区间进行排序.将关系变为三种. 然后进行处理.
* 区间的关系有三种:
* 第一种是完全没有交集的.
* 第二种是有交集,不是子集
* 第三种是:有交集,是子集.
*/
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] here, int[] there) {
if (here[0] != there[0]) {
return here[0] - there[0];
} else {
return here[1] - there[1];
}
}
});
//左侧是最小的.
List<int[]> result = new ArrayList<int[]>();
result.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
int[] interval = intervals[i];
int[] top = result.get(result.size() - 1);
if (interval[0] <= top[1]) {
//有交集
if (interval[1] >= top[1]) {
top[1] = interval[1];
}
//子集忽略
} else {
//无交集,之间的结束
result.add(interval);
}
}
return result.toArray(new int[result.size()][]);
}
}
986. 区间列表的交集
题解:
class Solution {
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
/**
* 求出交集的实现方式.首先将所有的元素进行排序,然后不断的求并集,然后依次用后面的和前面的取交集
*/
/**
* 这个题中,内部不相交,所以只需要和另外一个数组中的区间取交集就好了.如果一旦取过以后,就没有交集了.类似于归并排序.
*/
int firstRank = 0, secondRank = 0;
List<int[]> result = new ArrayList<>();
while (firstRank < firstList.length && secondRank < secondList.length) {
int low = Math.max(firstList[firstRank][0], secondList[secondRank][0]);
int high = Math.min(firstList[firstRank][1], secondList[secondRank][1]);
if (low <= high) {
result.add(new int[]{low, high});
}
if (firstList[firstRank][1] == high) {
firstRank++;
}
if (secondList[secondRank][1] == high) {
secondRank++;
}
}
return result.toArray(new int[0][2]);
}
}
57. 插入区间
题解:
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
boolean newAccepted = false;
int left = 0;
//这里套用了 归并排序模板
while (left < intervals.length || !newAccepted) {
int[] interval = null;
if (newAccepted) {
interval = intervals[left++];
} else if (left >= intervals.length) {
interval = newInterval;
newAccepted = true;
} else if (intervals[left][0] < newInterval[0] || (intervals[left][0] == newInterval[0] && intervals[left][1] < newInterval[1])) {
interval = intervals[left++];
} else {
interval = newInterval;
newAccepted = true;
}
if (result.size() == 0) {
result.add(new int[]{interval[0], interval[1]});
} else {
int[] top = result.get(result.size() - 1);
if (interval[0] <= top[1]) {
//有交集
if (interval[1] > top[1]) {
//交集集
top[1] = interval[1];
}
//子集不用管
} else {
//没有交集
result.add(new int[]{interval[0], interval[1]});
}
}
}
return result.toArray(new int[0][]);
}
}
标签：归并,int,interval,交集,算法,intervals,result,区间 From： https://www.cnblogs.com/xxuuzz/p/16626323.html