P1047 [NOIP 2005 普及组] 校门外的树

#include <bits/stdc++.h>
using namespace std;

int main() {
    int l, m;
    cin >> l >> m;

    vector<pair<int, int>> seg(m);
    for (int i = 0; i < m; i++) cin >> seg[i].first >> seg[i].second;

    // 按起点升序排序（插入排序：每次把当前区间挪到它该在的位置）
    for (int i = 1; i < m; i++) {
        for (int j = i; j > 0 && seg[j].first < seg[j - 1].first; j--) {
            swap(seg[j], seg[j - 1]);
        }
    }

    // 合并重叠区间，累加被移走的树数
    int removed = 0;
    int curL = seg[0].first, curR = seg[0].second;
    for (int i = 1; i < m; i++) {
        if (seg[i].first <= curR) {
            // 与当前段重叠，把右端点推到更远的地方
            curR = max(curR, seg[i].second);
        } else {
            // 断开，当前段结算
            removed += curR - curL + 1;
            curL = seg[i].first;
            curR = seg[i].second;
        }
    }
    removed += curR - curL + 1;

    cout << l + 1 - removed << "\n";
    return 0;
}