NC214017. Charging
描述
Xxy is the king of the universe. In order to resist the invasion, he ordered the construction of many space warships.Now,he wants to charge his space ships.
He has N space ships.The N ships are numbered from 1 to N and lined up in order.
Xxy has M charging plans.The i-th plan is describe by two positive integers li,ri.It means in this plan, he will charge the ships numbered from li to ri.
Xxy will choose some of these plan.If he totally choose tot plans,x is the number of ships that charged in every plans.Xxy want to maximize the value of min(tot,x).
输入描述
The first line contains two positive integers N and M(N,M≤300000).
The next M lines,each containing two positive integers li and ri.(li≤ri)
输出描述
The output contains a positive integer. The maximal value of min(tot,x).
示例1
输入:
3 3 1 3 2 2 1 2
输出:
2
C++(clang++11) 解法, 执行用时: 223ms, 内存消耗: 16584K, 提交时间: 2020-11-16 17:53:11
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
vector <int> v[maxn];
multiset <int> s;
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int t1,t2;scanf("%d%d",&t1,&t2);v[t1].push_back(t2);
}
int ans=1;
for(int i=1;i<=3e5;i++){
for(int j:v[i]) s.insert(j);
while(s.size()&&(*s.begin())-i+1<s.size()) s.erase(s.begin());
ans=max(ans,(int)s.size());
}
cout<<ans<<endl;
}