两组区间的相交元素个数

    
        标签：
        
            笔试算法题
        
    发布于：2022-03-19 13:15:39
    编辑于：2022-03-22 21:43:58
    浏览量：344

概述

如题。

LeetCode 我做过类似的题。

解法

先 merge 每组区间中相连的区间，之后循环遍历两组区间，有三种情况：

front 和 back 不相交
front 把 back 完全包裹
front 和 back 部分相交

复制粘贴导致我一个循环变量搞错了，要不是我检查断点处数据是否 okay，不然还发现不了。

之后由于变量名命名过于随意，导致后面循环里用的不是 merge 后的区间。。。

再之后忘记考虑上面的第二种情况了。。。几天不刷题有点搞哇！

#include <bits/stdc++.h>

using namespace std;

struct range {
    int l, r;
};

void merge(vector<range> &ranges, vector<range> &output) {
    sort(ranges.begin(), ranges.end(), [](const range &a, const range &b) -> bool {
        if (a.l != b.l) {
            return a.l < b.l;
        } else {
            return a.r > b.r;
        }
    });
    output.push_back({0, -1});
    for (auto &range: ranges) {
        if (range.l <= output.back().r) {
            output.back().r = max(output.back().r, range.r);
        } else {
            output.push_back(range);
        }
    }
}

int main() {
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    vector<range> aRanges(m1);
    for (int i = 0; i < m1; i++) {
        cin >> aRanges[i].l;
    }
    for (int i = 0; i < m1; i++) {
        cin >> aRanges[i].r;
    }
    vector<range> bRanges(m2);
    for (int i = 0; i < m2; i++) {
        cin >> bRanges[i].l;
    }
    for (int i = 0; i < m2; i++) {
        cin >> bRanges[i].r;
    }
    vector<range> as, bs;
    merge(aRanges, as);
    merge(bRanges, bs);
    int i = 1, j = 1;
    int count = 0;
    while (i < as.size() && j < bs.size()) {
        auto frontRangeP = &as;
        auto backRangeP = &bs;
        auto frontIdxP = &i;
        auto backIdxP = &j;
        if (bs[j].l < as[i].l) {
            frontRangeP = &bs;
            backRangeP = &as;
            frontIdxP = &j;
            backIdxP = &i;
        }
        if ((*backRangeP)[*backIdxP].l > (*frontRangeP)[*frontIdxP].r) {
            (*frontIdxP)++;
        } else if ((*backRangeP)[*backIdxP].r <= (*frontRangeP)[*frontIdxP].r) {
            count += (*backRangeP)[*backIdxP].r - (*backRangeP)[*backIdxP].l + 1;
            (*frontRangeP)[*frontIdxP].l = (*backRangeP)[*backIdxP].r + 1;
            (*backIdxP)++;
        } else {
            int right = (*frontRangeP)[*frontIdxP].r;
            int left = (*backRangeP)[*backIdxP].l;
            count += right - left + 1;
            (*backRangeP)[*backIdxP].l = (*frontRangeP)[*frontIdxP].r + 1;
            (*frontIdxP)++;
        }

    }
    cout << count;
}

Links: 两组区间的相交元素个数