题目

题解思路

左端点从小到大，对右端点从大到小，这样保证了初始节点的最优，再根据两个极限情况特判 初始节点的左端点大于1，或者右端点等于t。

这样我们只要在初始节点的基础上上，贪心的 找到左节点符合要求右节点又能最远的情况。

这个贪心策略很容易想到，但是代码实现还是有点难，用了大量标记来解决。

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct qj
{
    int x,y;
}a[25010];
bool cmp(qj A, qj B)
{
    if (A.x == B.x )
        return A.y > B.y;
    return A.x < B.x;
}
int main ()
{
    ios::sync_with_stdio(false);
    int n,t;
    cin>>n>>t;
    for (int i = 0 ; i < n ; i++ )
    {
        int t1,t2;
        cin>>t1>>t2;
        a[i].x = t1;
        a[i].y = t2;
    }
    sort(a,a+n,cmp);
    if (a[0].x > 1 )
        cout<<"-1\n";
    else
    {
        if (a[0].y == t )
        {
            cout<<"1\n";
            return 0;
        }
        int p1 = a[0].y,p2 = a[0].y ,ans = 1,book = 1, p = 1;
        while(1)
        {
            int book1 = 0;
            for (int i = p ; i < n ; i++ )
            {
                if (a[i].x -1 <= p1 && a[i].y > p2 )
                {
                    p2 = a[i].y;
                    p = i+1;
                    book1 = 1;
                }
            }
            if (!book1)
                break;
            ans++;
            p1 = p2;
            if (p2 == t )
            {
                book = 0;
                break;
            }
        }
        if (book)
            cout<<"-1\n";
        else
            cout<<ans<<"\n";
    }
    return 0;
}