[BOJ] 1263번 시간 관리 (C++)

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

1263번: 시간 관리

 

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

bool compare(pair<int, int>& a, pair<int, int>& b) {
	return a.second > b.second;
}

int main() {
	int n, t, s, tmp = 0, left = 0;
	cin >> n;

	vector<pair<int, int>> v(n);
	for (int i = 0; i < n; i++) {
		cin >> t >> s;
		v.push_back({ t, s });
	}

	sort(v.begin(), v.end(), compare);

	for (int i = 0; i < n; i++) {
		if (i != 0) {
			if (v[i].second >= tmp) left += v[i].second - tmp;
			else if (tmp - v[i].second >= left) left = 0;
			else if (tmp - v[i].second < left) left -= tmp - v[i].second;
		}
		tmp = v[i].second - v[i].first;
	}

	if (left > 0) tmp -= left; 

	if (tmp < 0) cout << -1 << endl;
	else cout << tmp << endl;

	return 0;
}

 

 

끝내야할 시간(t)와 걸리는 시간(s)를 입력받아 벡터에 넣는다. 끝내야할 시간이 늦은 일이 먼저 오도록 정렬한다.

 

맨 처음 끝내야할 시간이 가장 늦은 일에서  t - s는 시작하는 시간(tmp)이다. 

 

그 다음 1) 일을 끝내야할 시간이 이전 일을 시작하는 시간(tmp)보다 늦다면

현재 일을 끝내야할 시간 - 이전 일을 시작하는 시간

은 겹치기 때문에 left에 저장해둔다.

 

2) 일을 끝내야할 시간이 이전 일을 시작하는 시간(tmp)보다 빠르다면

시간이 남은 것이므로 left에 저장해둔 일을 할 수 있다.

- 남은 시간이 left보다 많거나 같다면 left를 모두 해서 0이 되고

- left보다 적다면 left에서 남은 시간을 뺀다.

 

마지막에 left가 남았다면 tmp에서 left를 빼준다. tmp는 일을 최대한 늦게 시작하는 시간이 된다.

tmp가 0보다 작다면 0시부터 시작하여도 일을 끝마칠 수 없는 것이므로 -1을 출력하고

그렇지 않으면 tmp를 출력한다.