AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

ABC131 D - Megalomania

問題原文

atcoder.jp

問題要旨

所要時間が  a_i、 締め切りが  b_i であるような仕事が  N 個与えられる。
1度に1つしか仕事ができない時、順番を工夫することで全ての仕事を締め切りに間に合うように終わらせることは可能か?

解法

よく見るスケジューリング問題。 締め切りが早いものから処理して損することがない。例えば、「締め切り9のものを後回しにするとギリギリ締め切り10に間に合う」なんて状況があっても、それは結局締め切り9には間に合わないので。
締め切り順にソートしてシミュレーションして終わり。

実装

N = int(input())
tasks = [list(map(int, input().split())) for i in range(N)]

tasks.sort(key=lambda x: x[1])
time = 0
for a, b in tasks:
    time += a
    if time > b:
        print('No')
        break
else:
    print('Yes')

感想

損しない 、ABC-D でよく見る気がします。 いつでも考えられるようにしておいて、その正しさの示し方もセンスとして身に付けたいですね。