首先按照左端点排序(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; }