1 solutions
-
-1
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define l first #define r second const int N=1e5+10; PII q[N]; int main() { int n; cin>>n; for(int i=0;i<n;i++) { cin>>q[i].l>>q[i].r; } sort(q,q+n); //按照区间左端点排序 priority_queue<int,vector<int>,greater<int> > heap; //小根堆 for(int i=0;i<n;i++) { if(heap.size()==0||heap.top()>=q[i].l) //组为空,或者是所有组的区间右端点都大于等于当前区间左端点 { heap.push(q[i].r); //新开一个 } else //在最小的后面加入当前区间 { heap.pop(); heap.push(q[i].r); } } cout<<heap.size(); return 0; }
- 1
Information
- ID
- 249
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 5
- Tags
- # Submissions
- 17
- Accepted
- 4
- Uploaded By