C++14(g++5.4) 解法, 执行用时: 20ms, 内存消耗: 564K, 提交时间: 2020-09-08 15:04:47

#include<bits/stdc++.h>
using namespace std;
struct node{
    int be,ed;
};

bool cmp(node &a,node &b)
{
    if(a.be==b.be)
        return a.ed<b.ed;
    return
        a.be<b.be;
}

int main()
{
    int N,T;
    cin>>N>>T;
    node a[25500];
    for(int i=1;i<=N;i++)
    {
        cin>>a[i].be>>a[i].ed;
    }
    sort(a+1,a+1+N,cmp);
    /*for(int i=1;i<=N;i++)
    {
        cout<<a[i].be<<" "<<a[i].ed<<endl;
    }*/
    if(a[1].be!=1)
        cout<<-1<<endl;
    else
    {
        int ans=0;
        int left=1;
        int right=0;
        int cnt=1;
        while(right<T)
        {
            left=right+1;
            for(int i=cnt;i<=N;i++)
            {
                if(a[i].be<=left&&a[i].ed>=left)
                {
                    right=max(right,a[i].ed);
                }
                if(a[i].be>left)
                {
                    cnt=i;
                    break;
                }
            }
            if(left>right)
                break;
            else
                ans++;
        }
        if(right<T)
        cout<<-1<<endl;
        else
            cout<<ans<<endl;

    }
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 11ms, 内存消耗: 652K, 提交时间: 2022-09-21 16:09:46

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using PII = pair<int, int>;

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<PII> a(n);
    for (auto &[x, y] : a) {
        cin >> x >> y;
    }

    sort(a.begin(), a.end(), [&](PII x, PII y){
        return x.first < y.first;
    });

    int ans = 0;
    for (int l = 1, j = 0; l <= m; l++) {
        int r = 0;
        while (j < n and a[j].first <= l) {
            r = max(r, a[j].second);
            j++;
        }
        if (r < l) {
            cout << -1 << '\n';
            return 0;
        }
        l = r;
        ans++;
    }
    cout << ans << '\n';
    return 0;
}

C++ 解法, 执行用时: 18ms, 内存消耗: 644K, 提交时间: 2022-01-30 10:08:53

#include<bits/stdc++.h>
using namespace std;
int n,m,nw,bd,ans;
struct node{int st,ed;}t[25001];
bool cmp(node x,node y){return x.st<y.st;}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>t[i].st>>t[i].ed;
	sort(t+1,t+n+1,cmp);
	while(nw<=n){
		int rs=0;
		while(nw<=n&&t[nw].st<=bd+1)rs=max(rs,t[nw++].ed);
		if(!rs)break;
		++ans;
		bd=max(bd,rs);
		if(bd>=m)break;		
	}
	if(bd<m)cout<<-1;
	else cout<<ans;
	return 0;
}