Megalomania [AtCoder Beginner Contest 131 D]

https://atcoder.jp/contests/abc131/tasks/abc131_d

前提知識

• 区間スケジューリング

解説

https://atcoder.jp/contests/abc131/submissions/6077645

この問題はほぼ区間スケジューリング問題である。
区間スケジューリングを解くには終了時間が最も早い仕事から終わらせる貪欲法である。
今回もそれで貪欲にすすめていき、全て締切までに終わればYes。
区間スケジューリングを知らないと解くのは難しいかもしれない。

int N, A[201010], B[201010];
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
string solve() {
	vector<int> ord;
	rep(i, 0, N) ord.push_back(i);
	sort(all(ord), [&](int a, int b) { return B[a] < B[b]; });

	int t = 0;
	rep(i, 0, N) {
		int a = A[ord[i]];
		int b = B[ord[i]];

		t += a;
		if (b < t) return no;
	}

	return yes;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> A[i] >> B[i];

	cout << solve() << endl;
}