ABC103 D - Islands War
問題
一直線にN個の島がN-1本の橋で繋がっている
島a[i]とb[i]を行き来できなくしてほしい、という形の要望M個を全て叶えるために取り除く必要のある橋の本数の最小値を求める
解法
クエリをa[i]の降順に見ていき、取り除いた橋の中で一番左の橋の番号rを保持しておく
rが[a[i],b[i])に含まれていればそのクエリはもう達成されている
そうでない場合は[a[i],b[i])のどれかの橋を取り除く必要があるが、a[i]を取り除くのが最善
(今後見るクエリのaは全部a[i]以下だから左に寄せるのが一番カバーできるクエリが多くなる)
int n, m, r = inf, res; vector<pair<int,int> > a; signed main() { cin >> n >> m; a.resize(m); rep(i,m) cin >> a[i].first >> a[i].second; sort(a.rbegin(), a.rend()); rep(i,m) if (a[i].second<=r) res++, r = a[i].first; cout << res << endl; }