Войти Регистрация
Алгоритмы

122. Меньше всего остановок на зарядку

Сложная

Электромобиль Яндекс Такси выезжает из точки 0 к точке target (в километрах) с запасом хода charge км. Вдоль дороги станции stations: пара [position, add] — станция на километре position добавляет add км запаса.

Батарея большая, переполнения нет. Доехать до станции можно, если position не больше текущей дальности. Верните наименьшее число остановок, чтобы доехать до target, или −1, если не получится.

В работе: Межгород из Москвы в Тверь, 180 км, на борту 70 км запаса: на каких зарядках останавливаться, чтобы потерять меньше времени.

Пример 1

Ввод
stations = [[30, 40], [60, 90], [100, 20], [150, 10]]
target = 180
charge = 70
Вывод
2

Станция на 60-м км даёт 70 + 90 = 160 — мало; вторая остановка, например на 100-м км, даёт ровно 180.

Пример 2

Ввод
stations = [[20, 100]]
target = 100
charge = 10
Вывод
-1

До первой станции не доехать: −1.

Ограничения

  • 1 ≤ target ≤ 10⁹
  • 0 ≤ charge ≤ 10⁹
  • 0 ≤ число станций ≤ 10⁵
  • 0 < position < target, 1 ≤ add ≤ 10⁹
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def min_charging_stops(stations, target, charge):
Жадный алгоритмКучацельO(n log n)

Источник: наша задача на данных Яндекса. Условие пересказано своими словами.