An orchard manager is protecting a single long row of fruit trees from a coming frost. Each tree sits at some position along the row and also has a recorded canopy height, which is kept purely for the orchard's records and has no bearing on frost protection. The manager has an unlimited supply of identical frostguard heaters. Once installed, a heater whose left edge sits at coordinate L warms every point in the half-open interval [L, L + w) along the row — the trailing edge at L + w itself is not warmed, because the heater's warm zone resets exactly there. Installed heaters may never overlap: their warm zones must be pairwise disjoint.
Determine the minimum number of heaters the manager must install so that every tree in the row ends up warmed.
The first line contains two integers n and w — the number of trees and the fixed heater width.
Each of the next n lines contains two integers x_i and y_i — the position and recorded canopy height of the i-th tree. Trees are not necessarily given in sorted order, and positions may repeat.
Print a single integer: the minimum number of heaters required so every tree is warmed.
Example 1
Input
5 3 1 5 2 8 3 1 6 2 10 4
Expected
3
Explanation
Sorting the trees by position gives x = 1, 2, 3, 6, 10 (canopy heights are irrelevant). The first heater's left edge is placed at 1, warming [1, 4); this also covers the trees at 2 and 3. The tree at 6 falls outside [1, 4), so a second heater starts at 6, warming [6, 9). The tree at 10 falls outside [6, 9), so a third heater starts at 10. In total, 3 heaters are needed.
Example 2
Input
4 5 2 1 3 9 8 4 9 2
Expected
2
Explanation
Sorted positions are 2, 3, 8, 9. The first heater starts at 2, warming [2, 7), which also covers the tree at 3. The tree at 8 lies outside [2, 7), so a second heater starts at 8, warming [8, 13), which also covers the tree at 9. Only 2 heaters are needed.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →