Вдоль трассы М-4 есть spots — километры, на которых арендодатели согласны поставить банкомат Сбера (заправки, кафе, придорожные магазины). Точки даны в произвольном порядке, на одном километре бывает несколько.
Нужно поставить ровно k банкоматов в разных точках из списка так, чтобы они покрывали трассу равномерно: наименьшее расстояние между двумя соседними банкоматами должно быть как можно больше.
Верните это наибольшее возможное наименьшее расстояние в километрах.
В работе: Расстановка банкоматов или терминалов, чтобы соседние не делили один поток клиентов.
Пример 1
spots = [120, 5, 300, 80, 210] k = 3
115
Точки 5, 120, 300: расстояния 115 и 180, наименьшее 115. Лучше не выйдет.
Пример 2
spots = [40, 40, 90] k = 2
50
Две точки на 40-м км: берём 40 и 90, расстояние 50.
Ограничения
- 2 ≤ k ≤ n ≤ 10⁵
- 0 ≤
spots[i]≤ 10⁹ - Лимит — 2 с на тест (2000 мс).
print() и console.log() уходят в консоль.
def atm_spread(spots, k):
Источник: наша задача на данных Сбера. Условие пересказано своими словами.
Ожидаемый ответ не нужен: покажем, что вернула функция.
Здесь появится результат отправки.