俩数组区间交集

image.png

双指针，注意单个数组的前面可能重叠，后面也可能。

遇到 [1,3],[2,4]这种重叠的记得left指针要抛弃[1,3]这种end更小的然后left++，因为下一个重叠肯定跟[1,3]没关系了。

如果没有重叠那就把前面那个指针++。

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        if(firstList.size()==0||secondList.size()==0){
            return {};
        }
        int l1=0;
        int l2=0;
        vector<vector<int>>res;
        // 看谁的start更小,然后判断是否有交集,有交集那么start更小但是end也更小的抛弃然后l1++,否则抛弃l2
        while(l1<firstList.size()&&l2<secondList.size()){
            int p1=max(firstList[l1][0],secondList[l2][0]);
            int p2=min(firstList[l1][1],secondList[l2][1]);
            if(p1<=p2){
                res.push_back(vector<int>{p1,p2});
                if(firstList[l1][1]<secondList[l2][1]){
                    l1++;
                }else{
                    l2++;
                }
            }else{
                if(firstList[l1][1]<secondList[l2][0]){
                    l1++;
                }
                else{
                    l2++;
                }
            }
        }
        return res;
    }
};