养猪场的道路

测试数据来自 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

寒假作业(二)

未认领
状态
已结束
题目
10
开始时间
2024-01-20 00:00
截止时间
2024-02-20 23:59
可延期
24.0 小时