算法1
$O(n + m)$
每次相交只有2个线段。 并且答案是 min(L1, L2) ~ max(R1, R2)。
一共有6种情况:
1. 相互离开 靠前的删除
2. 相交 R靠前的删除
C++ 代码
class Solution {
public:
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
vector<vector<int>> result;
int n = A.size();
int m = B.size();
int i = 0;
int j = 0;
while (i < n && j < m) {
if (A[i][1] < B[j][0]) {
i ++;
}
else if (B[j][1] < A[i][0]) {
j ++;
}
else {
result.push_back({max(A[i][0], B[j][0]), min(A[i][1], B[j][1])});
if (A[i][1] < B[j][1]) {
i ++;
}
else {
j ++;
}
}
}
return result;
}
};