农民约翰正在指挥他的N头牛进行清理工作。

他将一天划分为了T个班次(1~T)。

每头牛都只能在一天中的某一个时间段内进行不间断的工作。

你需要帮助约翰排列出一个合理的奶牛的清理班次,使得每个班次都有奶牛在进行清理,而且动用的奶牛数量可以尽可能的少。

输入格式
第1行:两个空格隔开的整数N和T。

第2…N+1行:第i+1行包含两个整数,分别表示第i头牛可以进行工作的开始时间和结束时间。

输出格式
输出一个整数,表示在每个班次都有奶牛清理的情况下,所需的奶牛最小数量。

如果无法做到每个班次都有奶牛清理,则输出-1。

数据范围
1≤N≤25000,
1≤T≤106
输入样例:
3 10
1 7
3 6
6 10
输出样例:
2
解题报告:这题其实就是区间覆盖的问题,问选择多少条区间可以覆盖整个区间,然后也可以dp做,dp数组定义为前i小时合法(包括第i小时),我们将区间按照右端点排序,因为只有将右端点排序才没有后效性,比如1 5
3 4 如果1 5 先来 那么3 4 的信息就更新不到5了,转移方程=f[r] = min(f[r],f[l-1~r-1]+1),看了好久都不大懂,后来才发现,区间是可以相交的 r不一定只被l-1所更新,只要在l-1到 r-1的范围都可以使用l~r这条线段。接下来就是复杂度的分析 复杂度O(n^2),会超时,那么就线段树优化,维护区间最小值即可。
代码:

#include<iostream>
#include<cstring>
using namespace std;
const int N=1000010;
const int INF=1e9;
int p = 1;
struct node{
   
    int l;
    int r;
    int minv;
}tr[N*4];
int n,m;
void build(int u,int l,int r)
{
   
    tr[u]={
   l,r,INF};
    if(l==r)
    return ;
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
void mdf(int u,int x,int d)
{
   
    if(tr[u].l==x && tr[u].r==x)
    {
   
        tr[u].minv=d;
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(x<=mid  )    mdf(u<<1,x,d);
    else            mdf(u<<1|1,x,d);
    tr[u].minv=min(tr[u<<1].minv,tr[u<<1|1].minv);
}
int query(int u,int l,int r)
{
   
    if(tr[u].l>=l && tr[u].r<=r)
        return tr[u].minv;
    int mid=tr[u].l+tr[u].r>>1;
    int res=INF;
    if(l<=mid)  res=min(res,query(u<<1,l,r));
    if(r>mid)   res=min(res,query(u<<1|1,l,r));
    return res;
}
typedef pair<int,int> pii;
pii q[N];
bool cmp(pii a,pii b)
{
   
    if(a.second !=b.second)
        return a.second < b.second;
    return a.first < b.first;
}
int main()
{
   
    cin >> n >> m;
    for(int i=0;i<n;i++)
    {
   
        cin >> q[i].first >> q[i].second;
    }
    build(1,0,m);
    mdf(1,0,0);
    sort(q,q+n,cmp);
    for(int i=0;i<n;i++)
    {
   
        int l=q[i].first;
        int r=q[i].second;
        int minv=min(query(1,l-1,r-1) + 1,query(1,r,r) );
        mdf(1,r,minv);
    }
    cout << (query(1,m,m)==INF ? -1 : query(1,m,m))<<endl;
    return 0;
    return 0;
 }