/*以所有奶牛的开始工作时间进行排序,要注意的一点是3 41 21 31 5有两头奶牛的初始时间相同时,一定要先选择结束时间晚的那个因为判断+1的条件是下一头奶牛的开始时间<=当前奶牛的终止时间+1，而终止时间>当前奶牛的终止时间 如上测试案例只需要一头奶牛,而如果不考虑起点相同选终点最晚的情况时测试结果为2
*/
#include <stdio.h>
#define N 25001
typedef struct cow
{int from;int to;
}Point;
Point p[N];
void quick_Sort(Point p[],int left,int right)
{int i=left,j=right;int pivot=p[(i+j)/2].from;Point temp;while (i<=j){while(p[i].from<pivot) i++;while(p[j].from>pivot) j--;if(i<=j){if(p[i].from==p[j].from&&p[i].to>=p[j].to){i++;j--;continue;}else{temp=p[i];p[i]=p[j];p[j]=temp;i++;j--;}}}if(i<right) quick_Sort(p,i,right);if(left<j) quick_Sort(p,left,j);
}
int solve(int n,int t)
{if(p[1].from>1){return -1;}int flag=1,last=1; //flag作为判断能否成功的标志,last作为初始的节点for(int i=2;i<=n;i++){if(p[i].from<=p[last].to+1&&p[i].to>p[last].to) //该节点初始位置在上一个节点终止前且结束位置在上一个节点终止后{//寻找左侧能全部覆盖而右侧最大的那个牛int j=i; //暂存第一个满足条件的i的值while (p[i].from<=p[last].to+1&&i<=n) //在所有节点中找开始位置在上一节点终止前且终止位置最靠右方的节点{if(p[i].to>p[j].to){j=i; //更新j}i++;}last=j; //last变为新找到的节点flag++;i=j; //当前节点变为找到的j节点if(p[last].to>=t) //已经可以覆盖到终止位置了,退出循环{break;}}}if(p[last].to<t) return -1; //无法完成任务return flag;
}
int main()
{int n,t;scanf("%d %d",&n,&t);for(int i=1;i<=n;i++){scanf("%d %d",&p[i].from,&p[i].to);}quick_Sort(p,1,n);printf("%d\n",solve(n,t));return 0;
}
//po 2376类似的还有poj的1065题,都要注意初始节点相同而终点不同的情况