思路
注意这个条件:每个区间列表都是成对不相交的,并且已经排序。
透漏2个重要信息,1,区间内的线段是不相交的。2,已经排序。
单个区间内的线段不相交,可以省去好多判断,不相交就简单多了。
直接双指针走一遍就可以。左端点取大的,右端点取小的,这就是交集。然后谁的右端点小移动谁。
独立版-结构体
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n;
struct node{
int l,r;
node(){}
node(int x,int y):l(x),r(y){}
};//一开始忘了分号了,汗
vector<node> A,B,res;
void jiaoji(){
if(A.empty()||B.empty()) return;
int i=0,j=0;
while(i<A.size()&&j<B.size()){
int start=max(A[i].l,B[j].l);//这里i和j弄混了
int end=min(A[i].r,B[j].r);
if(start<=end){
res.push_back(node(start,end));//这里用到node的构造函数
}
A[i].r<B[j].r?i++:j++;
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
A.push_back(node(a,b));
}
for(int i=0;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
B.push_back(node(a,b));
}
jiaoji();
for(int i=0;i<res.size();i++){
printf("%d,%d ",res[i].l,res[i].r);
}
printf("\n");
return 0;
}
力扣版
class Solution {
public:
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
if (A.empty() || B.empty()) {
return {};
}
vector<vector<int>> res;
int i = 0,j=0;
while (i < A.size() && j < B.size()) {
int start = max(A[i][0], B[j][0]);//i和j别弄错了
int end = min(A[i][1], B[j][1]);
if (start <= end) {
res.push_back({start, end});
}
A[i][1] < B[j][1] ? i++ : j++;
}
return res;
}
};
判断原来还可以这样写,学到了👍