우선순위큐를 이용한 그리디 문제.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

/*

1. 작업의 수행이 요청된 시간 그리고 그 작업을 수행하는 데 소요되는 시간이 서로 다르거나 같은 
   수개의 작업이 있고, 이들 작업은 한 번에 하나씩만 처리할 수 있다. 어느 한 작업을 처리하는 
   중일 때 다른 작업이 요청된 시간이 지나면, 그 작업은 시작되지 않고 대기된다.
   모든 작업을 다 수행한다 할 때, 요청된 시간부터 종료된 시간까지의 시간의 평균을
   최소로 하도록 작업 순서를 배치해 수행하도록 한다. 그 최소 평균 시간을 구하는 문제.
   
2. 다음 알고리즘으로 문제를 풀 수 있다.
   (1) 작업 시간이 들어있는 배열(이하 jobs)을 작업이 빨리 시작하는 순서대로 정렬한다.
   (2) 작업 시간이 가장 짧은 작업이 루트에 오도록 우선순위큐를 구성하는데, 
       우선순위큐에는 항상 '현재 수행중인 작업이 끝나는 시간(work_until)' 전에
       요청된 작업들만 넣는다.
   (3) 우선순위큐에서 루트노드를 빼 그 루트노드에 해당하는 작업을 수행하게 한다.
       (=전체 작업시간에 작업시간 + 요청시간을 추가하고, work_until에 그 작업의 수행시간을 더한다.)


*/


#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct cmp {
    bool operator()(pair<int, int> a, pair<int, int> b) {
        return a.second > b.second;
    }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;

int solution(vector<vector<int>> jobs) {
    sort(jobs.begin(), jobs.end());

    int answer = 0, work_until = jobs[0][0], i=0;
    pq.push({jobs[i][0], jobs[i++][1]});
    
    while(pq.empty() == false)
    {
    	int request_time = pq.top().first, work_time = pq.top().second;
        
        work_until += work_time;
        answer += work_until - request_time;
        
        pq.pop();
        
        for (; i < jobs.size(); i++)
            if (jobs[i][0] < work_until)
                pq.push({jobs[i][0], jobs[i][1]});
            else break;
            
        if(pq.empty() && i < jobs.size())
            pq.push({jobs[i][0], jobs[i++][1]});
    }
    
    return answer/jobs.size();
}