問題概要

東西に一列に並ぶ$N$個の島と, それをつなぐ$N - 1$個の橋がある.

「$a_i$と$b_i$の間を行き来できないようにしろ」という要望が$M$個寄せられた.

取り除かなければならない橋の本数の最小値を求めよ.

制約

  • $2 \leq N \leq 10^5$
  • $1 \leq M \leq 10^5$
  • $1 \leq a_i < b_i \leq N$

考察

$b_i$をソートして, それぞれの$b_i$の左隣の橋を崩していくのが最適っぽい. (区間スケジューリングっていうらしい)

とりあえず要望をvector<pair<int,int>>にぶち込んで, secondでソートする.

そのsecondを順番に辿って行って, 隣の橋($b_i - 1, b_i$間)を崩したときに要望を達していたらそれを$(-1, -1)$にして判定の対象外にして…, を繰り返す.

提出コード(C++🔆)

signed main() {
    SS(int, N, M);
    vpii request;
    REP(i, M) {
        SS(int, a, b);
        request.PB(MP(--a, --b));
    }
    int res = 0;
    sort(all(request), SORT_SECOND);
    REP(i, M) {
        if (request[i].first < 0) continue;
        int x = request[i].second;
        REP(j, i, M) {
            if (between(request[j].first, 0, x)) {
                request[j].first  = -1;
                request[j].second = -1;
            }
        }
        ++res;
    }
    cout << res << endl;
}