两组区间的相交元素个数
概述
如题。
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: 两组区间的相交元素个数