Solution
The solution to this problem is straightforward and no tricks are there as such. Think of it as the “merge” step of merge sort where you employ a two pointer technique. We have two pointers, P1 and P2, pointing to an interval of A and B respectively. Consider following cases:
- P1 and P2 do not overlap a. start(P1) > end(P2): Interval P1 is after interval P2 so increment P2 (go to next interval in B). b. end(P1) < start(P2): Interval P1 is before interval P2 so increment P1 (go to next interval in A).
- P1 and P2 overlap: In this case, the starting point of intersection will be max(start(P1), start(P2)) and ending point will be min(end(P1), end(P2)). We should increment the one who’s ending point is smaller. To understand this, consider these intervals: ``` A: [[2, 6], [7, 9]] B: [[1, 8]]
Intersection of first intervals of A and B: [2, 6] Now, if we increment P1, we get another intersection [7, 8] but if we had incremented P2 then we would have gotten no other intersection.
vector<vector
for (int i=0, j=0; i<A.size() && j<B.size();) {
if (A[i][0]>B[j][1])
j++;
else if (A[i][1]<B[j][0])
i++;
else {
ans.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 ans; } ``` Time complexity: O(max(A, B)) where A and B are sizes of the arrays