【ABC103】D - Islands War

問題概要

東西に一列に並ぶN個の島と、それをつなぐN-1個の橋がある。 a_iとb_iの間を行き来できないようにしろ、という要望がM個寄せられた。 取り除かなければならない橋の本数の最小値を求めよ。

制約

• 2 <= N <= 10⁵
• 1 <= M <= 10⁵
• 1 <= a_i < b_i <= N

考察

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

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

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

ACコード(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;
  }
  P(res);
}

Submission #3101715 - AtCoder Beginner Contest 103