【AtCoder版！蟻本】ABC103 D - Islands War【区間スケジューリング】

AtCoder版！蟻本の区間スケジューリングの例題としてあげられているABC103 D - Islands WarをPythonで解いていきます。

リンク

D - Islands War

ABC103 D - Islands War

問題文

東西一列に並んだ N 個の島と N−1 本の橋があります。i 番目の橋は、西から i 番目の島と西から i+1 番目の島を接続しています。
ある日、いくつかの島同士で争いが起こり、島の住人たちから M 個の要望がありました。

要望 i: 西から ai 番目の島と西から bi 番目の島の間で争いが起こったために、これらの島をいくつかの橋を渡って行き来できないようにしてほしい

あなたは橋をいくつか取り除くことでこれら M 個の要望全てを叶えることにしました。
取り除く必要のある橋の本数の最小値を求めてください。

制約

・入力は全て整数である
・2≤N≤10^5
・1≤M≤10^5
・1≤ai

解答例

n, m = map(int,input().split())

Point = []
for i in range(m):
    a, b = map(int,input().split())
    Point.append([a, b])

Point.sort(key = lambda x:x[1])

res = 1
tmp = Point[0][1] - 1
for i in range(m):
    if tmp < Point[i][0]:
        res += 1
        tmp = Point[i][1] - 1

print(res)

解説

東西に直線状にならんだN個の島とN-1本の橋があり、M個の島同士の対立関係があります。
すべての対立関係の島の間にある橋を壊し行き来できなくするためには、最小でいくつの橋を壊す必要があるか答える問題です。

争いが起こっている西からai番目の島とbi番目の島をPointリストに格納し、biについてソートします。

bi番目の島の西にかかる橋を壊すとして、tmp変数に壊した橋の位置を記憶しました。
tmpより東の位置がaiだった場合は、新たに橋を壊す必要があるので、resに1を足してtmpを更新します。
biについてソート済みなのでtmpとaiを比較すれば必要性を判断することができました。

このループを抜けたあとに解答となるresを出力すればOKです。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク