[Programmers 42627]ディスクコントローラ(Python)


質問する


https://programmers.co.kr/learn/courses/30/lessons/42627


『これは完全にSJFだよ~~背中のrgrgをちゃんと覚えてる』と叫んで解いた
思ったより時間がかかりました

問題を解く

작업 소요 시간이 짧은 순소요 시간이 같다면 요청 시점이 빠른 순で並べ替えます.
0.入力を受信して並べ替える
import heapq
from collections import deque

def solution(jobs):
    answer = 0
    h = []
    curr = sys.maxsize
    temp = []
    for j in jobs:	# j :(작업 요청 시점, 소요 시간)
        heapq.heappush(h, (j[1], j[0]))
        if j[0] < curr:
            curr = j[0]
curr가장 짧은 소요 시간を貯蔵した.
1.お尻の最初の要素とcurrを比較する
while h:
    while h and curr < h[0][1]:
        time, arrived = heapq.heappop(h)
        heapq.heappush(temp,(time,arrived))
必要な時間がcurrより長い場合は、取り出してtempに挿入します.힙의 최상단 요소의 소요 시간currに等しいまで繰り返します.
2.お尻が空いているかチェック
実はcurrの価格は一番短い時間がかかります.
お尻が空いていないと思います.

ドアがなくて、運行中にエラーが発生しました.
質問板をよく調べて、原因が分かりました.
🔗 テスト19..。実行時エラー...
」タスク終了後に実行される次のタスクは、現在の時点よりも遅くなる可能性があります.
しかし、コンサルティングcurr < h[0][1]の条件を満たすことができないため、
お尻のすべての要素がポップになります
したがって、お尻が空いている場合はcurrを1増加させる.
以上の条件が満たされるまで繰り返す
   if not h:
        curr += 1
    else:
        # 힙에 요소가 있으면 pop 해준다.
        time, arrived = heapq.heappop(h)
        # 현재 시점인 curr에 소요 시간을 더해준다.
        curr += time
        # answer에 대기 시간을 더해준다.
        answer += (curr - arrived)
3.temp要素をお尻に再び入れる
    while temp:
        t = heapq.heappop(temp)
        heapq.heappush(h, t)
一時保留のtempさらにhに入れます.
4.hとtempに要素がないまで繰り返す
5.出力平均ヒステリシス時間
    return (answer//len(jobs))

コード#コード#

import sys
import heapq
from collections import deque

def solution(jobs):
    answer = 0
    h = []
    curr = sys.maxsize
    temp = []
    for j in jobs:
        heapq.heappush(h, (j[1], j[0]))
        if j[0] < curr:
            curr = j[0]

    while h:
        while h and curr < h[0][1]:
            time, arrived = heapq.heappop(h)
            heapq.heappush(temp,(time,arrived))
        if not h:
            curr += 1
        else:
            time, arrived = heapq.heappop(h)
            curr += time
            answer += (curr - arrived)
            
        while temp:
            t = heapq.heappop(temp)
            heapq.heappush(h, t)
            
    return (answer//len(jobs))