Islands War [AtCoder Beginner Contest 103 D]

https://beta.atcoder.jp/contests/abc103/tasks/abc103_d

考察過程

1. 入力例1の答えが1である理由、入力例2の答えが2である理由を考えてみる
2. 自明なことを考えてみる「被らない2つの区間はそれぞれ橋を取り除かないと駄目」
3. 被っている区間があれば、うまくやればどちらも消せる
4. 被らないように区間を取った時に取れる最大個数が答えになるのでは？という天啓（区間スケジューリング）
5. ABCなんで落ちてもいいかなという気持ちで投げるとAC

前提知識

• 区間スケジューリング

解法

https://beta.atcoder.jp/contests/abc103/submissions/2886649

区間スケジューリングに帰着させて解く。
今回の答えは区間スケジューリングの答えと等しくなる。
区間スケジューリングは貪欲法で解けるのだが、それを忘れていてDPで解いてしまった。
　
dp[i] := [0,i)で共通部分の持たないように区間を選ぶときの最大個数
これを作ろう。
わかりにくいがO(N+M)となる。

int N, M;
vector<int> AB[101010];
int dp[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        AB[a].push_back(b);
    }
 
    rep(i, 1, N + 1) {
        chmax(dp[i], dp[i - 1]);
        fore(j, AB[i]) chmax(dp[j], dp[i] + 1);
    }
 
    cout << dp[N] << endl;
}