[프로그래머스/C++] 디스크 컨트롤러 풀이

문제 해석

---

---

문제 풀이

---

운영체제 시간에 배운 CPU Job scheduling 문제 같았다.

처음에 activity selection problem으로 생각해서 헤맸는데 우선순위 큐 문제이다.

1. job을 시작 시간 기준으로 오름차순 정렬한다.
2. 현재 시간보다 작거나 같은 job을 모두 우선순위 큐에 넣는다.
3. 우선순위 큐는 빨리 끝나는 job을 top으로 올리도록 설정한다.
4. job을 실행한 후 큐에서 pop한다.
5. 2~4번을 큐가 빌 때까지 반복한다

---

코   드

---

#include <bits/stdc++.h>
using namespace std;

struct compare
{
    bool operator()(vector<int> lhs, vector<int> rhs)
    {
        return lhs[1] > rhs[1] ;
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0, now = 0, idx= 0, N = jobs.size() ;
    sort(jobs.begin(), jobs.end(), greater<>()) ;
    priority_queue<vector<int>, vector<vector<int>>, compare> pq ;
    pq.push(jobs.back());
    jobs.pop_back();
    
    while(!pq.empty())
    {
        auto top = pq.top(); pq.pop();
        
        now = max(now + top[1], top[0] + top[1]) ;
        answer += now - top[0] ;
        
        while(!jobs.empty() && jobs.back()[0] <= now)
        {
            pq.push(jobs.back()); jobs.pop_back();
        }
        
        if(pq.empty() && !jobs.empty())
        {
            pq.push(jobs.back()); jobs.pop_back();
        }
    }
    return answer / N ;
}

---

느낀점: 세상에 고수는 많고 PS는 하면 할 수록 어렵다...

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

프로그래머스