[디스크 컨트롤러/LV3/Python3, C++]

다리를 지나는 트럭 LV2

 

문제 설명
하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 이 문제에서는 우선순위 디스크 컨트롤러라는 가상의 장치를 이용한다고 가정합니다. 우선순위 디스크 컨트롤러는 다음과 같이 동작합니다. 어떤 작업 요청이 들어왔을 때 작업의 번호, 작업의 요청 시각, 작업의 소요 시간을 저장해 두는 대기 큐가 있습니다. 처음에 이 큐는 비어있습니다. 디스크 컨트롤러는 하드디스크가 작업을 하고 있지 않고 대기 큐가 비어있지 않다면 가장 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 이때, 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 우선순위가 높습니다. 하드디스크는 작업을 한 번 시작하면 작업을 마칠 때까지 그 작업만 수행합니다. 하드디스크가 어떤 작업을 마치는 시점과 다른 작업 요청이 들어오는 시점이 겹친다면 하드디스크가 작업을 마치자마자 디스크 컨트롤러는 요청이 들어온 작업을 대기 큐에 저장한 뒤 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 또, 하드디스크가 어떤 작업을 마치는 시점에 다른 작업이 들어오지 않더라도 그 작업을 마치자마자 또 다른 작업을 시작할 수 있습니다. 이 과정에서 걸리는 시간은 없다고 가정합니다. 각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 정수 배열 jobs가 매개변수로 주어질 때, 우선순위 디스크 컨트롤러가 이 작업을 처리했을 때 모든 요청 작업의 반환 시간의 평균의 정수 부분을 return 하는 solution 함수를 작성해 주세요.


제한 사항
1 ≤ jobs의 길이 ≤ 500
jobs [i]는 i번 작업에 대한 정보이고 [s, l] 형태입니다.
s는 작업이 요청되는 시점이며 0 ≤ s ≤ 1,000입니다.
l은 작업의 소요시간이며 1 ≤ l ≤ 1,000입니다.


입출력 예

jobs	return
[[0, 3], [1, 9], [3, 5]]	8

 

알고리즘 고득점 Kit의 힙 문제 중 하나이다.

 

 

작업 시작 시간이 현재 시간보다 작을 때는 항상 디스크 내에 있는 작업으로 진행한다.

 

현재 시간보다 크고, 디스크의 작업이 비어있다면 현재 시간을 변경한다.

시작 시간이 맞지 않을 때의 문제에 대한 케이스를 해결해야 한다.

 

 

 

#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <deque>
#include <algorithm>
#include <queue>

using namespace std;



int solution(vector<vector<int>> jobs) 
{
    priority_queue<tuple<int, int, int>> pq; // 기본은 최대 힙임
    // 이를 최소 힙으로 만들기 위해 튜플에 <-소요 시간, -시작 시간>를 넣음에 주의
    
    for(int i=0; i<jobs.size(); i++)
        jobs[i].push_back(i);
    sort(jobs.begin(), jobs.end());
    
    
    int time = jobs[0][0]+jobs[0][1];
    int result = jobs[0][1];
    
    for(int i=1; i<jobs.size(); ++i)
    {
        while(!pq.empty() && time < jobs[i][0])
        {
            auto tp = pq.top(); pq.pop();
            time -= get<0>(tp);
            result += (time + get<1>(tp));
        }
        
        if(time < jobs[i][0])
        {
            time = jobs[i][0] + jobs[i][1];
            result += jobs[i][1];
            continue;
        }
        pq.push(make_tuple(-jobs[i][1], -jobs[i][0], -jobs[i][2]));
    }
    
    while(!pq.empty())
    {
        auto tp = pq.top(); pq.pop();
        time -= get<0>(tp);
        result += (time + get<1>(tp));
    }
    
    return result / jobs.size();
}

 

 

import heapq

def solution(jobs):
    jobs.sort()
    heap = []

    endTime = jobs[0][1] + jobs[0][0]
    answer = jobs[0][1] + jobs[0][0]

    for i in range(1, len(jobs)):
        while len(heap) > 0 and endTime <= jobs[i][0]:
            endTime += heapq.heappop(heap)
            answer += endTime

        if jobs[i][0] > endTime:
            endTime += jobs[i][0] - endTime
        heapq.heappush(heap, jobs[i][1])


    while len(heap) > 0:
        endTime += heapq.heappop(heap)
        answer += endTime
        
    
    for i in range(len(jobs)):
        answer -= jobs[i][0]
        
    return answer // len(jobs)

 

 

 

---