[Heap] 디스크 컨트롤러

<문제>

[Heap] 디스크 컨트롤러 문제

<문제 풀이>

 

work(작업 시작 요청 시간, 작업 시간) 이렇게 데이터가 주어지고,

작업의 시작 요청 시간에서부터 작업을 마치기 까지의 총 시간(=total end time)이 가장 적은 방향으로 스케줄러를 짜야 한다.

 

모든 작업을 완료했을 때, total end time의 평균이 가장 작으면 된다.

 

total end time을 계산하는 방법은

 

현재 work end time = 전체 작업 시간 - 현재 work의 요청 시간.

 

따라서 모든 work의 end time은

 

1.작업을 처리할 때 마다 누적 작업 시간을 계산한다.

workingTime += work[i][1];

(=workingTime에는 첫번째 work의 작업시간 + 두번째 work의 작업시간 + ... + n번째 work의 작업시간)

 

2.누적 작업 시간에서 작업 요청 시간을 빼서 누적 end time의 합 구한다.

totalEndTime += workingTime - work[i][0];

(=totalEndTime에는 총 작업시간에서 현재 작업의 요청 시간을 뺀 시간(end time) == 첫번째 end time + 두번째 end time + ... + n번째 end time)

 

3.단, 만약 현재 작업의 요청 시간(work[i][1])이 이전 누적 작업 시간보다(workingTime) 크다면 

누적 작업 시간은 현재 작업의 요청시간으로 초기화 된다.

if(workingTime < work[i][1]) workingTime = work[i][1];

(이유: 현재 작업 요청 시간이 누적 작업 시간보다 크다면, 이전의 누적 작업 시간이 영향을 미치지 못하기 때문이다.)

 

 

 

---

이 후, heap을 이용하여 데이터를 작업 시간(최소힙)으로 정렬한다.

 

priority_queue<vector<int>, vector<vector<int>>,compare> pq; 

 

여기서 compare는 구조체 또는 클래스로 구성하는데,

 

class compareWorkingTime{
    public:
    
    bool operator()(vector<int> a, vector<int> b){

    if(a[1] == b[1]) {
         return a[0] < b[0];
     }
     return a[1] > b[1]; 
    }
};

 

이런식으로 구성하였다.

 

 

<코드 구현>

 

-내 풀이-

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

using namespace std;


class compareStartTime{
    public:
    
    bool operator()(vector<int> a, vector<int> b){

    
    if(a[0] == b[0]) {
         return a[1] > b[1];
     }
     return a[0] > b[0]; 
    }
};

class compareWorkingTime{
    public:
    
    bool operator()(vector<int> a, vector<int> b){

    
    if(a[1] == b[1]) {
         return a[0] < b[0];
     }
     return a[1] > b[1]; 
    }
};

int endTime = 0;
int accumulTime =0;

void computeTime(int startTime, int workingTime, bool flag){
    if(flag) {
        endTime += startTime - endTime;
        accumulTime += workingTime;
    } else accumulTime += endTime + workingTime - startTime; 
    endTime += workingTime;
}

int solution(vector<vector<int>> jobs) {
    int answer = 0;

    priority_queue<vector<int>, vector<vector<int>>, compareStartTime> pq1(jobs.begin(), jobs.end());
    priority_queue<vector<int>, vector<vector<int>>, compareWorkingTime> pq2;
    
    if(pq1.top()[0] != 0) 
        computeTime(pq1.top()[0], pq1.top()[1], true);
    else computeTime(pq1.top()[0], pq1.top()[1],false);
    pq1.pop();
    
    while(!pq1.empty()) {
        if(pq1.top()[0] > endTime) {
            computeTime(pq1.top()[0], pq1.top()[1], true);
            pq1.pop();
        }
        
        else {
            while(pq1.top()[0] <= endTime) {
                pq2.push(pq1.top());
                pq1.pop(); if(pq1.empty()) break;
            }
            
            computeTime(pq2.top()[0], pq2.top()[1],false);
            pq2.pop();
            
            while(!pq2.empty()) {
                pq1.push(pq2.top());
                pq2.pop();
            }
        }
    }
    
    answer = floor(accumulTime/jobs.size());

    return answer;
}

했는데 시간이 너무걸림.

 

-다른 사람 풀이-

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;

class CompareProcessTime{
    public:
        template <class T = std::vector<int> >
        bool operator () (T& a, T& b) const{
            return a[1]>b[1];
        }
};

class CompareInputTime{
    public:
        template <class T = std::vector<int> >
        bool operator () (T& a, T& b) const{
            return a[0]<b[0];
        }
};

int solution(vector<vector<int> > jobs) {
    int answer = 0;

    std::priority_queue<vector<int>,vector<vector<int> >, CompareProcessTime> PQ;

    std::sort(jobs.begin(),jobs.end(),CompareInputTime());
    int time = jobs[0][0];
    auto iter = jobs.begin();
    while(iter != jobs.end()||!PQ.empty()){
        while(iter!=jobs.end()&&(*iter)[0]<=time){//작업이 이미 도착해있다면
            PQ.push(*iter++); //도착해 있는 작업들을 모두 Priority Queue에 넣음
        }

        if(!PQ.empty()){
                time += PQ.top()[1]; //작업을 수행한다.
                answer += (time - PQ.top()[0]); //처음 들어온 시간부터 수행 된 시간 까지의 차이를 뺀다.
                PQ.pop();     
        }
        else{
            time = (*iter)[0];
        }
    }

    answer /= jobs.size();
    return answer;
}