/ Vijos / 题库 /

泥泞道路

泥泞道路

时间限制:1秒  内存限制:256M


【题目描述】

  牧场里下了一场暴雨,泥泞道路上出现了许多水坑,约翰想用一批长度为 \(L\) 的木板将这些水坑盖住. 

  牧场里的道路可以看成一根数轴,每个水坑可以用数轴上的两个坐标表示,如 \((3,6)\) 表示从 \(3\) 到 \(6\) 有一个长度为 \(3\) 的水坑。所有的水坑都是不重叠的,\((3,6)\) 和 \((6,9)\) 可以出现在同一个输入数据中,因为它们是两个连续的水坑,但不重叠。

  请你帮助约翰计算最少要用多少块木板才能将所有水坑盖住。

【输入格式】

  第 1 行有二个用空格隔开的整数 \(N\) 和 \(L\)。其 \(N\),表示水坑总数,\(L\) 为木板长度。
  接下来的 \(N\) 行每行两个整数 \(s_i\) 和 \(e_i\) ,表示一个水坑的左端点坐标和右端点坐标。

【输出格式】

  一个整数,表示约翰盖住所有水坑最少要用多少块长为 \(L\) 的木板.

【输入输出样例】

 Input

3 3
1 6
13 17
8 12

 Output

5

【数据限制】

  对于 \(100\%\) 的数据,\(1≤N≤10000\),\(0≤s_i<e_i≤10^9\)。

【来源】

  Mr.he

信息

ID
1795
难度
9
分类
贪心 | 其他 | 排序 点击显示
标签
递交数
3
已通过
1
通过率
33%
被复制
2
上传者