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)