Description
有m个椅子，第i个在位置i，每个椅子只能坐一个人。 有n个人，第i个人能坐的椅子的位置j需满足j≤Li或j≥Ri。 现在你可以添加若干个椅子，可以放在任意实数位置。问最少加多少个
Input
第一行两个整数N,MN,M
接下来NN行，每行两个整数Li,RiLi,Ri
Output
输出最小需要增加的数量
Sample Input
Case 1:
4 4
0 3
2 3
1 3
3 4
Case 2:
7 6
0 7
1 5
3 6
2 7
1 6
2 6
3 7
Case 3:
3 1
1 2
1 2
1 2
Case 4:
6 6
1 6
1 6
1 5
1 5
2 6
2 6
Sample Output
Case 1:
0
Case 2:
2
Case 3:
2
Case 4:
2
HINT
1≤N,M≤2∗1051≤N,M≤2∗105
0≤Li<Ri≤M+1(1≤i≤N)0≤Li<Ri≤M+1(1≤i≤N)
所有输入的数都是正整数
Sol
我们把左端点排序，然后用一个堆维护左边安排不下的人的r，每次如果还有空位置就直接放，没有的话就把堆里最大值和现在作比较，选择大的安排座位，小的放堆里
之后右边按顺序安排即可。
Code
#include <bits/stdc++.h>
using namespace std;
int n,m,L,R,hr[200005],ans;priority_queue<int,vector<int>,greater<int> >h;vector<int>hl[200005];char c;
int main()
{
scanf("%d%d",&n,&m);
for(int i=0,l,r;i<n;i++) scanf("%d%d",&l,&r),hl[l].push_back(r);
for(int i=1,t;i<=m;i++) for(vector<int>::iterator it=hl[i].begin();it!=hl[i].end();it++)
{
if(L<i){L++,h.push(*it); continue;}
t=h.top();
if(t>=*it) hr[*it]++;
else h.pop(),hr[t]++,h.push(*it);
}
for(vector<int>::iterator it=hl[0].begin();it!=hl[0].end();it++) hr[*it]++;
R=m+1;ans=hr[m+1];
for(int i=m;i;i--) for(;hr[i]>0;hr[i]--) if(i<R&&L<R-1) R--;else ans++;
printf("%d
",ans);
}