区间贪心:
- 区间选点
- 最大不相交区间
- 区间分组
- 区间覆盖
- 本题
Packing Under Range Regulations
该题目分解之后 就变为了 有N个任务,每个任务有一个起始日期和截至日期,一天只能完成一个任务,完成一个任务仅需要一天,问是否N个任务都能完成。
思路:为了使N个任务尽可能都完成,按照左端点排序(因为1天就能完成任务,尽量选早的那一天),优先放在左端点上,可以用一个小根堆来存储当前最小右端点,然后for循环来枚举模拟 当前任务是否能够完成
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
typedef pair <int, int> PII;
PII a[maxn];
int main()
{
int T;
scanf("%d", &T);
while(T --)
{
int N;
scanf("%d", &N);
for(int i = 1 ; i <= N ; i ++)
scanf("%d %d", &a[i].first, &a[i].second);
sort(a + 1, a + N + 1); //优先放在左端点上
priority_queue <int, vector<int>, greater<int>> pq;
int x = 0;
bool flog = true; // 1 1
a[N + 1] = {1e9 + 10, 1e9 + 10};// 1 1
for(int i = 1 ; i <= N + 1 && flog; i ++)
{
while(x < a[i].first && !pq.empty())
{
if(x > pq.top())
{
flog = false;
break;
}
pq.pop();
x ++;
}
x = a[i].first; //
pq.push(a[i].second);
}
if(flog) printf("YES\n");
else printf("NO\n");
}
return 0;
}