[c++] 백준 1263 시간 관리 - 그리디

[문제]

https://www.acmicpc.net/problem/1263

1263번: 시간 관리

 

[풀이]

그리디 알고리즘. 가장 늦게 끝내도 되는 시간 순으로 내림차순 정렬을 한다. 그 후 끝내야 하는 시간이 더 작으면 계속 갱신해준다.

예를 들어, 아래 테이블의 경우 가장 늦은 시간은 20시이다.

3 5
8 14
5 20
1 16

 

해당 일은 5시간이 걸리므로 20-5=15, 즉 적어도 15시에는 시작해야 한다. 만약 그 전 일인 16시까지 끝내야 하는 일을딱 16시에 맞춰서 끝냈다면 16+5=21>20이므로 뒤에 일을 시간 내에 끝내지 못한다. 따라서 16시까지 끝내는 것이 아닌 15시까지 끝내야 하는 일로 갱신되야 한다. 그 다음은 15-1=14이고 어차피 14시까지 끝내면 되는 일이므로 영향이 없다. 마찬가지로 14-8=6이고 이는 원래 끝내야 하는 시간인 5시보다 크므로 영향을 주지 않는다. 따라서 일을 최대한 늦게 시작하면 5-3=2시 부터 시작할 수 있다.

차이가 0보다 작아지면 0시부터 시작해도 일을 끝낼 수 없으므로 -1을 출력한다. 

 

[코드]

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace::std;

int main() {
    //걸리는 시간, 끝내야 하는 시간
    //마감시간 내 일을 모두 처리할 수 있는 범위 내에서 최대한 늦게 일을 시작할 수 있는 시간
    int N;
    cin >> N;
    vector<pair<int,int>> v(N);
    for(int i=0; i<N; i++){
        int a, b;
        cin >> a >> b;
        v.push_back({b, a});
    }

    //가장 늦게 끝나도 되는 일을 기준으로 내림차순 정렬
    sort(v.begin(), v.end(), greater<>());

    //20 5
    //16 1
    //14 8
    //5 3
    int diff;
    for(int i=0; i<N; i++){
        diff = v[i].first-v[i].second;
        if(i==N-1)
            break;
        if(diff < v[i+1].first)
            v[i+1].first = diff;
    }

    if(diff>=0)
        cout << diff;
    else
        cout << "-1";

}