[プログラマ]ディスクコントローラ-python


▼▼▼問題説明


HDDは一度に1台しか処理できません.ディスクコントローラを実装する方法はいくつかあります.最も一般的な方法は、リクエストの受信順序に従って処理することである.
例:
  • 0ミリ秒時3ミリ秒のA要求
  • Bジョブ要求
  • ミリ秒(
  • ミリ秒)
  • 2ミリ秒時6ミリ秒のC要求
  • 受け取った要求は同じです.下図のように.

    一度に1つのリクエストしか実行できないため、各タスクをリクエストの順序で処理する場合:
  • A:3ミリ秒(リクエストから終了まで:3ミリ秒)
  • B:1 ms待機開始、3 ms動作開始、12 ms完了(リクエストから終了:11 ms)
  • C:2ミリ秒から2ミリ秒、12ミリ秒から18ミリ秒(リクエストから終了:16ミリ秒)
  • 各タスクの要求から終了までの平均時間は10ミリ秒(=(3+11+16)/3)である.
    でもA→C→B順に処理すると
  • A:3ミリ秒(リクエストから終了まで:3ミリ秒)
  • C:2ミリ秒~2ミリ秒、3ミリ秒~9ミリ秒、7ミリ秒~
  • B:1 msで待機開始、9 msで作業開始、18 msで完了(リクエストから終了まで:17ミリ秒)
  • A→C→Bの順に処理すると,各タスクの要求から終了までの平均時間は9 ms(=(3+7+17)/3)となる.
    各タスクについて、「要求タスクの時点、タスク所要時間」を含む2 Dタイルジョブをパラメータとして指定した場合は、要求から終了までのタスクの平均値を最小限に抑えるためのソルバを作成します.(ただし小数点以下)

    ▼▼▼制限

  • 作業の長さは500を超えない.
  • ジョブの各ローは、単一のタスクの[タスクを要求する時間、タスクに必要な時間]です.
  • 各タスクの要求時間は1000時間を超えない.
  • 各操作について、
  • の所要時間は1000時間を超えない.
  • HDDが動作していない場合は、リクエストのタスクを先に処理してください.
  • 🎈 I/O例


    jobs : [[0, 3], [1, 9], [2, 6]]
    return : 9

    👩‍💻 マイコード


    初めて問題を解いた時、制限事項をよく読んでいなかったので、時間を無駄にしました.
    「ハードディスク(HDD)が機能していない場合は、リクエストのタスクを先に処理してください.」この文章を読んでおけば、ずっと易しくなります.
    今回もお尻の問題なのでDequeで解きます.問題は難しいと思って、時間がかかりましたが、一番大切なのはまだ完成していないことです.(コードも汚い)
    import heapq
    from collections import deque
    
    def solution(jobs):
        
        avg_time, finish_time, heap = 0, 0, []
        
        jobs.sort()
        d_jobs = deque(jobs)
        
        while(len(d_jobs) != 0):
            
            # 제일 처음 요청
            start_jobs = d_jobs.popleft()
            finish_time += (start_jobs[0] + start_jobs[1])
            avg_time += (finish_time-start_jobs[0])
    
            while (len(d_jobs) != 0):
                next_jobs = d_jobs.popleft()
                if next_jobs[0] <= finish_time: # 처음 작업 시간 사이에 요청 시간이 있는 작업인 경우
                    heapq.heappush(heap, next_jobs[1])
                else:
                    # print("next_jobs : ", next_jobs)
                    finish_time = 0
                    d_jobs.appendleft(next_jobs)
                    break
        
            while (len(heap) != 0):
                root = heapq.heappop(heap)
                for i in jobs:
                    if i[1] == root:
                        finish_time += root
                        avg_time += (finish_time - i[0])
                        # print("avg_time : ", avg_time)
                        break
        
        avg_time /= len(jobs)
        return int(avg_time)
    
            
    このようにして作られた結果はこうだった.

    本当にめまいが...まだ完成していないのにアップロードする理由は、私が実現した過程を確認したいからです.
    実は2次元配列で構成されているので複雑です...これさえ解决できないのか.早く解決したいようう