Charging Stops on an EV Route

easy

Electric-car drivers ask the maps app for a route and want to know, before they leave, how many times they will have to stop and charge. Every stop costs them half an hour, so the app should plan as few as possible.

The route is a straight road from kilometre 0 to kilometre distance. The car leaves with a full battery, which lasts batteryRange kilometres. Charging stations stand at the kilometre marks in stations, in no particular order (two stations can share a position). At a station the car can charge back to full.

Return the fewest charging stops needed to reach kilometre distance, or -1 if it cannot be reached at all. Arriving with an empty battery, exactly at a station or at the destination, is fine.

Example

distance = 100, batteryRange = 40, stations = [30, 60, 90].

On a full battery the car reaches kilometre 40, so it must stop at the station at 30. From there it reaches 70, so it stops again at 60, and from 60 it reaches 100. The answer is 2.

Example 1

Input

[
  "100",
  "40",
  "[30,60,90]"
]

Output

Explanation. The example.

Example 2

Input

[
  "50",
  "60",
  "[]"
]

Output

Explanation. The battery covers the whole route.

Example 3

Input

[
  "100",
  "30",
  "[20,50,80]"
]

Output

Explanation. Every station is needed.

Example 4

Input

[
  "100",
  "30",
  "[20,55,80]"
]

Output

-1

Explanation. From kilometre 20 the car reaches 50, and the next station is at 55.

Example 5

Input

[
  "120",
  "50",
  "[90,40,40,70,10]"
]

Output

Explanation. Unsorted, with a duplicate: stop at 40, then at 90.

Example 6

Input

[
  "60",
  "30",
  "[30]"
]

Output

Explanation. Arriving at a station with an empty battery is fine.

Example 7

Input

[
  "30",
  "30",
  "[]"
]

Output

Explanation. Arriving at the destination with an empty battery is fine.

Example 8

Input

[
  "10",
  "5",
  "[5,5,5]"
]

Output

Explanation. Three stations at the same place count as one stop.

Example 9

Input

[
  "1000",
  "200",
  "[150,300,340,520,700,760,880,990]"
]

Output

Explanation. Always charging at the farthest reachable station.

Example 10

Input

[
  "100",
  "10",
  "[20]"
]

Output

-1

Explanation. The first station is out of reach.

Example 11

Input

[
  "1000000000",
  "600000000",
  "[500000000]"
]

Output

Explanation. Large distances.

Follow-up: Stations now charge at different speeds, and the driver wants the least total time spent charging rather than the fewest stops. Does the greedy choice still work? What would you use instead?

Constraints:

- `1 <= distance <= 10^9` - `1 <= batteryRange <= 10^9` - `0 <= stations.length <= 10^5` - `0 < stations[i] < distance`

Views: 3