boj1263 시간관리
- 끝나는 시간에 맞춰 오름차순으로 정렬한 뒤 제일 마지막에 끝나는 시간부터 탐색한다.
- 탐색방법
- 제일 마지막 끝나는 시간부터 최소로 빠르게 끝낼수 있는 시간을 구한다.
- 이전 탐색결과까지 빠르게 끝낼수 있는 시간이 지금 탐색하고 있는 정보의 끝나는 시간보다 늦게 끝난다면 지금 끝나는 시간으로 update 해서 탐색
- 빠르게 끝낼수 있는 시간은 이전 최소로 빠르게 끝낼수 있는 시간 - 현재 탐색하는 정보의 걸리는 시간
- 소스코드
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int, int> pii;
vector<pii> v;
int n, s,t,now;
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d %d", &s, &t);
v.push_back({t,s});
now = max(now, t);
}
sort(v.begin(), v.end());
for (int i = n - 1; i >= 0; i--) {
if (now > v[i].first) now = v[i].first;
now -= v[i].second;
}
if (now < 0) printf("-1");
else printf("%d", now);
}
