目录
Description
有 \(n\) 个小球,每个小球必须在其所在的区间 \([l,r]\),问是否可以放下所有小球
State
\(1<=T<=2*10^5\)
\(1<=n<=2*10^5\)
\(1<=l<=r<=10^9\)
Input
2
3
1 2
2 3
3 3
5
1 2
2 3
3 3
1 3
999999999 1000000000
Output
Yes
No
Solution
很经典的贪心题,先将以光标 \(l\) 为左端点的区间存储起来,然后找到最紧急的区间,也就是 \(r\) 最小的那个,然后光标 \(l=l+1\),以此类推;
由于中间可能存在断点,所以需要利用二分快速找到下一个左端点
Code
const int N = 1e6 + 5;
int n, m, k, _;
pii a[N];
signed main()
{
//IOS;
rush(){
sd(n);
map<int, vector<int>> mp;
rep(i, 1, n){
sdd(a[i].fi, a[i].se);
mp[a[i].fi].push_back(a[i].se);
}
sort(a + 1, a + 1 + n);
a[++ n] = {2e9, 2e9};
priority_queue<int, vector<int>, greater<int>> q;
bool ok = 1;
for(int l = 0; l != 2e9;){
if(q.empty() && mp[l].empty()){
l = upper_bound(a + 1, a + 1 + n, mp(l, 0)) - a;
l = a[l].fi;
if(l == 2e9) break;
}
for(auto it : mp[l]) q.push(it);
int top = q.top();
if(top < l) ok = 0;
q.pop();
l ++;
}
if(ok) puts("Yes");
else puts("No");
}
//PAUSE;
return 0;
}