养猪场的道路
测试数据来自 system/2686
作业已超过截止时间,您无法递交本题目。
时间限制:1秒 内存限制:256M
【题目描述】
养猪场再次遭遇百年一遇的特大暴雨,前往猪圈的的道路上出现了许多水坑,猪场老板想用一些长度为 \(L\) 的石板来将这些水坑覆盖。
我们可以把猪场的道路看成数轴,用数轴上的两个坐标表示来表示每个水坑,如 \((4,8)\) 表示从 \(4\) 到 \(8\) 有一个长度为 \(4\) 的水坑。但是由于时间紧张,记录的水坑的坐标会出现重叠现象,如\((2,5)\) 和 \((4,8)\)这样的数据 ,但可以把它们看成连成一片的水坑。
那么老板最少要准备多少块石板才能将所有水坑覆盖?
【输入格式】
第一行包含两个整数 \(N\) 和 \(L\)。其中 \(N\) 表示水坑总数,\(L\) 为石板长度。
接下来的 \(N\) 行每行两个整数 \(a\) 和 \(b\) ,表示一个水坑的左端点坐标和右端点坐标。
【输出格式】
一个整数,表示老板盖住所有水坑需要石板的最少数量。
【输入输出样例】
Input
4 5
2 6
5 8
9 14
15 20
Output
4
【数据限制】
对于 \(100\%\) 的数据,\(1≤N≤10000\),\(0≤L≤10^9\),\(0≤a<b≤10^9\)。
【来源】
Mr.he