Ctrl K

Отрезки на графике

Средняя
Метеостанция записала показания readings: readings[i] = [day, value] означает, что в день day прибор показал value. Строится график: точки откладываются на плоскости (по оси X — день, по Y — значение) и соседние по дню точки соединяются. Несколько звеньев подряд, лежащих на одной прямой, рисуются одним отрезком. Верните наименьшее число отрезков, из которых складывается график. Показания в массиве не обязательно упорядочены по дням.
Пример 1
readings=[[4, 10], [1, 1], [2, 4], [3, 7], [5, 10]] → 2

По дням точки идут так: (1,1), (2,4), (3,7), (4,10) — один отрезок с наклоном 3, затем (4,10)–(5,10) — горизонтальный. Всего 2 отрезка.

Пример 2
readings=[[6, 2]] → 0

Одна точка — рисовать нечего, ответ 0.

Пример 3
readings=[[1, 5], [2, 3], [3, 5], [4, 3]] → 3

Пила: наклон всё время меняется, каждый из трёх кусков — отдельный отрезок.

Ограничения
  • 1 ≤ len(readings) ≤ 10⁵
  • readings[i] = [day, value]
  • 1 ≤ day, value ≤ 10⁹
  • Все day различны
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСамый маленький загон СредняяБлижайшие к базе точки СредняяРавные суммы окон на кольце СредняяПустые прямоугольники между точками СредняяПустой прямоугольник по точкам Средняя
загружаем Python…
Вход
readings=[[4, 10], [1, 1], [2, 4], [3, 7], [5, 10]]
Ожидается
2

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