[백준 6086] 시간 관리하기

문제

www.acmicpc.net/problem/6068

 

알고리즘

Greedy

 

풀이

일을 처리하는데 걸리는 시간, 일의 마감기한이 주어졌을 때 일을 시작해야하는 가장 늦은 시간을 구하는 문제입니다.

 

일을 마감기한에 딱 맞춰서 끝내는 것이 일을 가장 늦게 시작할 수 있을 것입니다. 마감기한이 가장 늦은 일부터 마감시간에 딱 맞게 일을 역순으로 처리해나가며 현재시간과 다음으로 처리해야할 일의 마감기한중 작은 값을 현재시간으로 취해나가며 시뮬레이션 하면 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

typedef pair<int, int> pii;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    vector<pii> vt;
    int N;
    cin >> N;
    rep(i, N) {
        int a, b;
        cin >> a >> b;
        vt.emplace_back(b, a);
    }
    sort(vt.rbegin(), vt.rend());
    int cur = INT_MAX;
    for (auto [b, a] : vt) {
        cur = min(cur, b);
        cur -= a;
    }
    cout << (cur < 0 ? -1 : cur);
    return 0;
}