ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

AtCoder-ABC131 D - Megalomania【Python解答例】

AtCoder ProblemsのRecommendationにあったABC131 D - Megalomaniaを解いていきます。


AtCoder Beginner Contest131 D - Megalomania

D - Megalomania

問題文

AtCoder王国の王立問題工房でABC管理官の座に就いたキザハシ君は、浮かれるあまり仕事を引き受けすぎてしまいました。
現在の時刻は 0 です。キザハシ君は 1 から N までの番号が振られた N 件の仕事を持っています。
キザハシ君が仕事 i を終えるには Ai 単位時間かかります。また、仕事 i の〆切は時刻 Bi であり、これまでに仕事を終わらせる必要があります。時刻 Bi ちょうどに仕事 i を終わらせてもかまいません。
キザハシ君は 2 件以上の仕事を同時にすることはできませんが、ある仕事を終わらせた直後に別の仕事を始めることはできます。
キザハシ君はすべての仕事を〆切までに終わらせることができるでしょうか。可能ならば Yes、不可能ならば No を出力してください。

制約

・入力はすべて整数
・1≤N≤2×10^5
・1≤Ai,Bi≤10^9(1≤i≤N)

解答例

n = int(input())

AB = []
for i in range(n):
    array = list(map(int, input().split()))
    AB.append(array)

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

time = 0
for i in range(n):
    time += AB[i][0]
    if time > AB[i][1]:
        print("No")
        break
else:
    print("Yes")

解説

N個の仕事があり、i番目の仕事は終わるのにAiだけ時間かかり、締め切りがBiです。
すべての仕事を〆切までに終わらせることができればYes、無理ならNoを出力する問題です。

AiとBiはABリストに格納しました。
AB[i] = [Ai, Bi]となるような二次元配列になります。

N個の仕事は、〆切が早い順 つまりBiが小さい順番で取り組むようにしました。
したがってABリストをBiについてソートしました。
二次元配列のソートについて過去に学習しましたので、参考までにリンクをはっておきます。
ebisuke33.hatenablog.com

あとはfor文ですべての仕事が間にあうか 判定していきます。
i番目についてtime変数にAiを足すことで仕事を終える時間になります。
timeが〆切のBi = (AB[i][1])より大きければ間に合わないことになりますのでNoを出力します。
すべて間に合うならYesを出力するようにすればACでした。



〆切が近い順に仕事に取り組むほうがいいよなって思いつきでそのまま解くことができました。
2次元配列のソートはまだ慣れていないので、数多く解いていきたいです。