leetcode 986 区间列表的交集

题目地址

由于每个列表的区间都是互不重叠且排好序的，所以可以利用归并排序的方法，从两个列表的头上取出来两个小区间判断

之后删除掉较小的那个

判断两个区间的交点的代码如下

1
2
3
4
5
int lo = max(firstList[p1][0],secondList[p2][0]);
int hi = min(firstList[p1][1],secondList[p2][1]);
if(lo<=hi){
    ret.push_back({lo,hi});
}

如果没有交点，lo会比hi大，否则证明二者有交点

最后去掉较小的区间，继续比较，就是个正常的归并排序

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        int n = firstList.size();
        int m = secondList.size();
        vector<vector<int>> ret;
        int p1 = 0;
        int p2 = 0;
        while(p1<n&&p2<m){
            int lo = max(firstList[p1][0],secondList[p2][0]);
            int hi = min(firstList[p1][1],secondList[p2][1]);
            if(lo<=hi){
                ret.push_back({lo,hi});
            }
            if(firstList[p1][1]>secondList[p2][1]){
                p2++;
            }else{
                p1++;
            }
        }
        return ret;
    }
};