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

서론

운영체제의 SJF(Shortest Job First)에서 착안한 문제인것 같다.

풀이

예제를 통해 작업시간이 짧은것부터 우선적으로 처리하는게 효율적이라는걸 유추할 수 있다.

그러나 작업시간이 짧은것을 먼저 처리하기 위해 하드디스크가 쉬고 있는데 이미 요청을 받은 다른 작업을 기다리게 하고 작업시간이 짧은것을 요청받을때까지 기다리지는 않는다.

요청을 받은 작업들 중 작업시간이 짧은것을 먼저 처리하기 위해 min-heap의 우선순위 큐를 이용한다.

시간이 0초부터 1초씩 증가하면서 jobs에 요청을 받은 작업이 있는지 확인한다.

아직 없다면 시간을 계속 증가시켜주고

있다면 요청받은 작업을 우선순위 큐로 옮긴다. 요청받은 작업이 여러개라면 모두 옮긴다.

큐에 작업이 들어오면 우선순위 큐를 이용해서 작업시간이 가장 짧은 작업을 가져와서 작업시간만큼 시간을 증가시키고 요청부터 종료까지의 시간을 저장한 후 해당 작업은 버린다. 작업이 하나 끝나면 jobs를 다시 확인해서 요청받은게 있는지 확인하고 있다면 큐로 이동시킨다.

그리고 다시 큐에서는 작업시간이 짧은 작업을 처리한다.

이를 큐와 jobs가 텅빌때까지 반복한다.

구현

// c++

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

using namespace std;

int solution(vector<vector<int>> jobs) {
    int vSize = jobs.size();
    int time = 0;
    int sum = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
    
    sort(jobs.begin(), jobs.end());

    while(!jobs.empty() || !pq.empty()){
        while(1){
            if(!jobs.empty() && jobs[0][0] <= time) {
                pq.push({jobs[0][1], jobs[0][0]});
                jobs.erase(jobs.begin());
            } else{
                break;
            }
        }
        if(!pq.empty()){
            time += pq.top().first;
            sum += time-pq.top().second;
            cout<<time<<endl;
            pq.pop();
        } else {
            time++;
        }
    }

    return sum / vSize;
}