首先按照左端点排序(pair类型自动按首键排序),然后扫一遍,有重叠就先别处理,没有重叠就直接加上刚刚那部分即可
代码实现很简单:
#define pb push_back
void solve() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> a;
while (m--) {
cin >> t >> k;
a.pb({t, k});
}
sort(a.begin(), a.end());
int l = 0;
for (auto p : a) {
if (p.first >= l) ans += p.first - l - 1;
l = max(p.second, l);
}
cout << ans + n - l + 1;
return;
}

京公网安备 11010502036488号