NOIP模拟 梦境（贪心）

内网传送门

【题目分析】

感觉和防晒霜一题差不多，所以考试的时候一直在想贪心，举反例把自己举死多次后老老实实打网络流的暴力去了qwq

结果正解还是贪心hehe

以每段区间的左端点作为关键字进行排序，对每一个点去考虑进行分配。肯定优先考虑先消失的区间，即右端点小的区间，所以开一个优先队列记录右端点，每次处理一个点时先将所有右端点已经在该点左侧的区间删掉，加入左端点在当前点左侧的区间，最后看优先队列是否为空，如果不为空就用最快消失的区间。

【代码~】

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10;

int n,m,pos=1;
int ans;
pair<int,int> a[MAXN];
int b[MAXN];
priority_queue<int> q;

int Read(){
	int i=0,f=1;
	char c;
	for(c=getchar();(c>'9'||c<'0')&&c!='-';c=getchar());
	if(c=='-')
	  f=-1,c=getchar();
	for(;c>='0'&&c<='9';c=getchar())
	  i=(i<<3)+(i<<1)+c-'0';
	return i*f;
}

int main(){
	n=Read(),m=Read();
	for(int i=1;i<=n;++i)
	  a[i].first=Read(),a[i].second=Read();
	for(int i=1;i<=m;++i)
	  b[i]=Read();
	sort(a+1,a+n+1);
	sort(b+1,b+m+1);
	for(int i=1;i<=m;++i){
		while(pos<=n&&a[pos].first<=b[i])
		  q.push(-a[pos].second),++pos;
		while(!q.empty()&&-q.top()<b[i])
		  q.pop();
		if(!q.empty())
		  ans++,q.pop();
	}
	cout<<ans;
	return 0;
}