算法
(贪心) $O(N\log N)$
显然优先做截止时间靠前的工作,所以我们可以先把这些工作按截止时间排序,然后扫描每一个工作,计算做完当前工作的时间并判断它有没有超过相应的截止时间。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
using P = std::pair<int, int>;
int main() {
int n;
cin >> n;
vector<P> p(n);
rep(i, n) cin >> p[i].second >> p[i].first;
sort(p.begin(), p.end());
ll t = 0;
rep(i, n) {
t += p[i].second;
if (t > p[i].first) {
puts("No");
return 0;
}
}
puts("Yes");
return 0;
}