ABC103 D - Islands War

問題

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

解法

貪欲的に解けます。 まず、bの値が小さい順に各要望をソートします。 ソートした要望を先頭からiterateし、叶えられていない要望を見つけるたびに、その要望を叶えられる橋のうち最も東の橋を取り除きます。 この方法により取り除いた橋の数が求める解です。

ACしたコード

from functools import reduce
from operator import itemgetter

N, M = map(int, input().split())
a, b = zip(*(map(int, input().split()) for _ in range(M)))
ts = sorted(zip(a, b), key=itemgetter(1))
ans = reduce(
    lambda acc, t: acc if t[0] < acc[1] else (acc[0] + 1, t[1]),
    ts,
    (0, 0)
)[0]
print(ans)