ABC131 D – Megalomania

はじめに

競プロの精進のために学びがあった問題についてまとめています。
目標は AtCoder 水色！

今のレートは茶色です。

問題

ABC131 D – Megalomaniaを解きました。

キザハシ君は 2 件以上の仕事を同時にすることはできませんが、ある仕事を終わらせた直後に別の仕事を始めることはできます。
キザハシ君はすべての仕事を〆切までに終わらせることができるでしょうか。可能ならば Yes、不可能ならば No を出力してください。

難易度は茶色。

考察

典型的な貪欲問題。

仕事の期日の短い順にソートして貪欲法で解く。

コード

N = int(input())
T = []

for i in range(N):
    a,b = map(int,input().split())
    T.append((b, a))

T.sort()
now = 0
for t in T:
    now += t[1]
    if now > t[0]:
        print("No")
        exit()

print("Yes")

まとめ

とても簡単でした。