Boj2109_순회강연

Published: by Creative Commons Licence

boj2109 순회강연

  • n 값이 0이 들어올수 있어서 계속 런타임 에러가 발생했다..ㅠ
  • 아이디어 : 날짜가 제일 큰 날부터 하루씩 가능한 강의 중 가장 큰 값을 강연한다. (그리디)

  • max_heap 를 이용하여 문제 해결

  • 소스코드
#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);
}