986. Interval List Intersections

二路归并 O(m + n) time O(1) space
最简单的办法是取两个interval的交集，如果交集存在则存入结果，再「分别」判断『交集』的右边界和两个interval是否重合，重合则看下一个interval
这道题用扫描线做会非常复杂

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
        int m = A.size(), n = B.size();
        int i = 0, j = 0;
        vector<vector<int>> res;
        while (i < m && j < n) {
            int s = max(A[i][0], B[j][0]);
            int e = min(A[i][1], B[j][1]); // 找intersection
            if (s <= e) { // 如果有intersection
                res.push_back({s, e});
            }
            if (e == A[i][1]) { // 如果A[i]区间比较靠前则看下一个
                ++i;
            }
            if (e == B[j][1]) {
                ++j;
            }
        }
        return res;
    }
};