LeetCodeWeekly 237 1834. Single-Threaded CPU プライオリティキュー典型
題意
- $n$個の仕事がありそれぞれ、$a,b,c$のパラメータを持つ．
- aは$0..n-1$個目の仕事であるという仕事のindexである
- bは仕事に着手してもいい開始の時間である．つまり、その時間以上になるまで、その仕事は実施できない
- cはその仕事にかかる時間である
- ある瞬間、終わっていない仕事があるなら、cが最小、cが同じならaが最小のものから仕事に取り組む．これらの仕事の着手順序をインデックス(=a)で答えよ
こう考えた
まず、単にシミュレーションを行う問題であることは題意より明らかである．
２つのキューを持つことにする.
- $q1:まだ実施できない仕事の候補$．これらは、b(実施可能なる時間)が小さいものから取り出せるべきである．
- $q2:現在時刻として着手できる仕事の候補$．これらは、実施時間(c)が小さいものから取り出されるべきであり、その中でも、インデックス(a)が小さいものから取り出せるべきである．
これが準備できれば、時間を持ちつつ、$q2$のタスクを取り出し時間を経過させて、$q1$から実施できるタスクを取り出していけばいい．
注意は、$q2$がからの場合は$q1$からタスクを１つ取り出し、時間をそこに進める必要がある点か．
class Solution:
def getOrder(self, tasks: List[List[int]]) -> List[int]:
from collections import deque
from heapq import heapify, heappop, heappush
turn = 0
madamadatask = []
heapify(madamadatask)
korekaraq = []
heapify(korekaraq)
for i in range(len(tasks)):
enque, needtime = tasks[i]
heappush(madamadatask, (enque,needtime, i))
# madamada taskは全体のタスクをenqueの順番に並べたもの．
# 実施するタスクではなくて、今後実施できるようになるタスク
curtime = -1
res = []
# korekarataskはすでに実施できて、どれを実施するか迷うもの．
# これは、条件の通り、needtimeが最小、同じ場合はindexが最小の物を取り出す
while len(madamadatask) != 0 or len(korekaraq) != 0:
if len(korekaraq) == 0: # キューに仕事がないなら新しい仕事が必要．
# この場合、現在の時間に関係なく１つ取り出し、時間を開始時間まで飛ばす
enque, needtime, index = heappop(madamadatask)
heappush(korekaraq, (needtime, index, enque) ) #
curtime = enque
continue
# やるべき仕事がある場合、それを実施する
needtime, index, enque = heappop(korekaraq)
if curtime < enque:
curtime = enque
curtime += needtime
res.append(index)
# ここで時間は現在の実施後まで飛んでいるので、
# それで実施可能になった仕事をキューに入れる
while len(madamadatask) > 0:
enque, needtime, index = heappop(madamadatask)
if enque > curtime:
heappush(madamadatask, (enque ,needtime, index))
break
heappush(korekaraq, (needtime, index, enque) )
return (res)
Author And Source
この問題について(LeetCodeWeekly 237 1834. Single-Threaded CPU プライオリティキュー典型), 我々は、より多くの情報をここで見つけました https://qiita.com/recuraki/items/f761df23f58f90899435著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .