C++(g++ 7.5.0) 解法, 执行用时: 91ms, 内存消耗: 2936K, 提交时间: 2023-02-01 21:29:14

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

typedef pair<int, int> PII;

const int N = 300005;
int n, m, res;
PII w[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ ) scanf("%d %d", &w[i].fi, &w[i].se);
    sort(w + 1, w + m + 1);
    priority_queue<int, vector<int>, greater<int>> q;
    
    for (int i = 1; i <= m; i ++ )
    {
        q.push(w[i].se);
        while (q.top() - w[i].fi + 1 < q.size()) q.pop();
        res = max(res, min((int)q.size(), q.top() - w[i].fi + 1));
    }
    cout << res;
}

C++ 解法, 执行用时: 187ms, 内存消耗: 2936K, 提交时间: 2022-01-18 14:51:34

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
struct f{
	int l,r;
}p[N];
bool cmp(const f&a,const f&b){
	if(a.l!=b.l) return a.l<b.l;
	else return a.r<b.r;
}
int n,m,ans;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>p[i].l >>p[i].r ;
	sort(p+1,p+1+m,cmp);
	priority_queue<int,vector<int>,greater<int> >q;
	for(int i=1;i<=m;i++){
		q.push(p[i].r );
		while(q.top()-p[i].l+1<q.size()) q.pop();
		int k=q.size();
		ans=max(ans,min(k,q.top()-p[i].l+1));
	}
	cout<<ans;
}