ABC131 D - Megalomania
問題原文
問題要旨
所要時間が 、 締め切りが であるような仕事が 個与えられる。
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 でよく見る気がします。
いつでも考えられるようにしておいて、その正しさの示し方もセンスとして身に付けたいですね。