Ctrl K

Самая светлая точка улицы

Средняя
Прямая улица — это числовая ось, вдоль которой стоят фонари. Фонарь lamps[i] = [p, r] стоит в точке p и освещает все целые точки отрезка [p - r, p + r] включительно. Яркость точки — это количество фонарей, которые её освещают. Найдите целую точку с наибольшей яркостью и верните её координату. Если таких точек несколько, верните самую левую (наименьшую).
Пример 1
lamps=[[0, 3], [6, 2], [5, 1]] → 4

Фонари освещают отрезки [-3, 3], [4, 8] и [4, 6]. Точки 4, 5 и 6 освещены дважды, остальные — не больше одного раза. Самая левая из лучших — 4.

Пример 2
lamps=[[2, 0], [-1, 3]] → 2

Первый фонарь освещает только точку 2, второй — отрезок [-4, 2]. Дважды освещена лишь точка 2.

Пример 3
lamps=[[10, 5]] → 5

Единственный фонарь одинаково освещает весь отрезок [5, 15], ответ — его левый край.

Ограничения
  • 1 ≤ len(lamps) ≤ 10⁵
  • lamps[i] = [p, r]
  • -10⁸ ≤ p ≤ 10⁸
  • 0 ≤ r ≤ 10⁸
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСколько цветёт в день визита СложнаяСтудии для записи СредняяХватит ли мест в шаттле СредняяТабло заказов для кухни СредняяРасстановка под популярные отрезки Средняя
загружаем Python…
Вход
lamps=[[0, 3], [6, 2], [5, 1]]
Ожидается
4

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 114 тестов на сервере, включая скрытые.