백준 1263, 시간 관리

개요

문제 링크
실버 1, Greedy
모든 작업을 수행할 수 있는 최대시작시간 구하기

---

접근

1. 시작시간의 최댓값은 모든 작업의 시작시간의 최솟값이다. 따라서 작업을 정렬해야 한다. 나머지 구현은 어렵지 않았고, 정렬을 잘 찍어서 맞았다.

2. 핵심은 정렬, 어떻게? 작업의 끝이 빠른 순으로, 끝이 같다면 시작이 빠른 순으로

3. 이렇게 정렬해야 하는 이유? 반대로 생각하면 쉽다.
   만약 마지막 작업을 선택한다고 생각하자.

   1. 작업자는 게으르기 때문에 최대한 일을 미뤘다가 하고 싶어한다. 즉 가장 늦게 끝내도 되는 작업을 나중에 하고 싶어한다.
   2. 가장 늦게 끝내도 되는 작업이 여러개라면 가장 급한 것부터 해야 한다. 즉 시작을 가장 빨리해야 하는 작업부터 해야 한다. = 시작이 가장 느린 것을 마지막에 한다.

   늦게 끝내도 되는 것 = 끝이 느린 것
   급한 것 = 시작이 빠른 것
   마지막작업 = 가장 늦게 끝내도 되는 것 중에 가장 안 급한 것

   그래서 마지막 작업 = 끝이 느리고 시작이 느린 것이 된다.

4. 답 = max(모든작업시작) = min(작업들의 시작)이라고 했다.
   그러면 min(시작)을 해주면 답이 될까? 아니다.
   만약 {start, end} = {4,5}, {3,5}인 두 작업을 생각하면, 최소시작인 3을 골라버리면 {4,5}인 작업을 할 수 없다.

   머리로 생각하면 2에는 시작을 해야 3시간동안 두 작업을 끝낼 수 있다. 하지만 이렇게 복잡한 작업을 시킬 수는 없으니 되면 출력하고 안되면 시작을 1 줄여주면 된다.
   즉, min(시작)부터 0까지 시작시간을 줄여가며 되는지 확인하면 되는 것.

5. 어떤 시간이 유효한지 확인하는 법?
   앞에서 정렬한 것을 이용한다. 작업을 해나가는 과정에서 만약 지금 시간이 작업의 시작시간을 지나버렸다면 작업을 더 할 수 없다. 만약 작업이 가능하다면 현재 작업의 소모 시간을 더해주면 다음 시간이 자동으로 갱신된다.

---

Pseudo code

compare(a, b) {
    if (끝이 다르면)
        끝이 빠른 순으로
    else
        시작이 빠른 순으로
}
sort by compare;
valid(time) {
    for (q = 작업)
        if (q의 시작 < time)
            return 불가능
        time += q의 소모시간
    return 가능
}
for (time = min(starts) ~ 0)
    if (valid(time))
        answer = time
if (어떤 시간도 안됨)
    answer = -1

---

Source code

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

typedef struct {
    int s, e, t;
} task;

int c1(task a, task b) {
    if (a.e == b.e)
        return a.s < b.s;
    else
        return a.e < b.e;
}

int n;
task q[N];

int can(int t) {
    for (int i=0; i<n; i++) {
        if (q[i].s < t)
            return 0;
        t += q[i].t;
    }
    return 1;
}

int main() {
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> q[i].t >> q[i].e;
        q[i].s = q[i].e-q[i].t;
    }
    sort(q, q+n, c1);
    for (int t=q[0].s; t>=0; t--)
        if (can(t)) {
            cout << t;
            return 0;
        }
    cout << -1;
}