ABC103 D問題 Islands War を区間スケジューリングで解く

区間スケジューリングに慣れるためにABC103のD問題を解いてみました。
区間スケジューリングを実装できるようになった次のステップとして、良い問題だと思いました。

atcoder.jp

西から東へ一列に並んだN個の島と個の橋があります。
要望がM個あって、それぞれの要望は西から番目の島と西から番目の島で争いがおこったので、橋を渡って島を行き来できないようにして欲しい。
取り除く必要がある橋の最小値を出力する問題です。

例えば、1番目の島と5番目の島で争いが起こったら、1番目から5番目の間にある橋をどれか1つ取り除けば良いです。
絵を描いてイメージすると何となく区間スケジューリングで解くイメージがわきそうです。

問題のイメージ

まずは下準備として、の番号順でソートします。
最小の共通している橋の範囲をメモしておきます。
要望を受けて、その範囲と最小の共通している範囲がかぶっていたら、最小の共通している範囲をもっと小さくできないか確認して更新します。具体的にはと最小の範囲の左側を比較して、値が大きい方を最小の範囲の左側として更新します。
もし最小の共通している範囲と要望を受けた範囲がかぶっていなかったら、壊す橋の数をカウントアップして、最小の範囲を更新します。

ポイントは事前に右側の島の順でソートすることと、最小の共通している島の範囲に着目することかなと思います。

N, M = list(map(int, input().split()))
ab_list = []
for _ in range(M):
    a, b = list(map(int, input().split()))
    ab_list.append([a, b])

ab_list = sorted(ab_list, key=lambda x: x[1])
min_range = [ab_list[0][0], ab_list[0][1]]
ans = 1
for ab in ab_list:
    if ab[0] < min_range[1]:
        min_range[0] = max(min_range[0], ab[0])
        continue
    min_range = [ab[0], ab[1]]
    ans += 1
print(ans)