普通dp O(n^2)超时
二分优化O(nlogn)
f[i]定义为前i个区间的最大的牧草堆数
将所有草堆按右端点升序

代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int f[N];
int n;
struct lr{
    int l, r;
}w[N];

bool cmp(lr a, lr b)
{
    return a.r < b.r;
}

int bound(int l, int r, lr x)
{
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(w[mid].r < x.l)l = mid;
        else r = mid - 1;
    }
    return l;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> w[i].l >> w[i].r;
    }

    sort(w + 1, w + n + 1, cmp);

    for(int i = 1;i <= n;i++)//
    {
        f[i] = max(f[i - 1], f[bound(0, i - 1, w[i])] + w[i].r - w[i].l + 1);//j的右端小于i的左端 且f最大(f单调非减)
//      f[i] = f[i - 1];
//      for(int j = 0;j <= i - 1 && w[j].r < w[i].l;j++)O(n)优化
//      {
//          f[i] = max(f[i], f[j] + w[i].r - w[i].l + 1);
//      }

//      cout << f[i] << endl;
    }

    cout << f[n] << endl;
}