Level 3. 디스크 컨트롤러

Level 3. 디스크 컨트롤러

 

 

처음에 소요 시간으로만 정렬해 시작 시간을 빼 더하면 되는 줄 알았는데, 그게 아니어서 설명이 잘 돼 있는 이 블로그를 참고했다.

 

프로그래머스_힙(Heap)_디스크 컨트롤러 (JAVA)

 

소요 시간으로 정렬하되, 현재까지 소요된 시간들을 더해 그 중에서도 수행할 수 있는 가장 빠른 시작 시간을 가진 작업을 선택해야 하는 문제였다.

 

생각 외로 쉽지 않았다..

 

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

using namespace std;

struct Job
{
    int start;
    int duration;
};

class compare
{
public:
    bool operator()(const Job& A, const Job& B) { return A.duration > B.duration; }
};

int solution(vector<vector<int>> jobs)
{
    vector <int> answer;
    priority_queue<Job, vector<Job>, compare> minHeap;
    vector<Job> sortedJobs;
    int currentStart = 0, i = 0;

    for (auto& job : jobs)
        sortedJobs.emplace_back(Job{job[0], job[1]});

    sort(sortedJobs.begin(), sortedJobs.end(), [](Job& A, Job& B) { return A.start < B.start; });

    while (i < sortedJobs.size())
    {
        if (minHeap.empty())
            currentStart = max(currentStart, sortedJobs[i].start);

        while (i < sortedJobs.size() && sortedJobs[i].start <= currentStart)
            minHeap.emplace(Job{sortedJobs[i].start, sortedJobs[i].duration}),
            ++i;

        answer.emplace_back((currentStart += minHeap.top().duration) - minHeap.top().start);
        minHeap.pop();
    }

    while (!minHeap.empty())
    {
        answer.emplace_back((currentStart += minHeap.top().duration) - minHeap.top().start);
        minHeap.pop();
    }

    return accumulate(answer.begin(), answer.end(), 0) / answer.size();
}