Ctrl K

Собственное время функций

Средняя
Однопоточная программа вызывает count функций с номерами от 0 до count - 1. Вызовы образуют стек: в каждый момент выполняется функция на вершине стека, а вызывающая её ждёт. Время разбито на единицы с номерами 0, 1, 2, … Журнал logs содержит записи вида "номер:start:t" и "номер:end:t" в хронологическом порядке. start в момент t означает, что вызов начался в начале единицы t; end в момент t — что вызов закончился в конце единицы t. Функция может вызываться много раз, в том числе рекурсивно. Собственное время функции — сколько единиц времени она выполнялась сама, то есть была на вершине стека, по всем своим вызовам. Верните список длины count, где на месте i стоит собственное время функции i.
Пример 1
count=2, logs=["0:start:0", "1:start:3", "1:end:4", "0:end:8"] → [7, 2]

Функция 0 работает в моменты 0–2, затем функция 1 — в моменты 3 и 4, затем снова функция 0 — в моменты 5–8. Итого 3 + 4 = 7 и 2.

Пример 2
count=3, logs=["2:start:1", "2:end:1", "0:start:2", "0:start:4", "0:end:4", "0:end:5"] → [4, 0, 1]

Функция 2 занимает ровно одну единицу (момент 1). Функция 0 вызывает сама себя: внешний вызов работает в моменты 2, 3 и 5, вложенный — в момент 4, всего 4. Функция 1 не вызывалась.

Ограничения
  • 1 ≤ count ≤ 100
  • 1 ≤ len(logs) ≤ 500
  • 0 ≤ номер функции < count
  • 0 ≤ t ≤ 10⁹
  • Журнал корректен: у каждого start есть свой end, вызовы правильно вложены, записи идут по времени
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПостфиксный калькулятор СредняяПрямой обход дерева поиска СредняяНиз, пик и середина СредняяНаименьшая последовательность по стрелкам СредняяСледующее большее по кругу Средняя
загружаем Python…
Вход
count=2, logs=["0:start:0", "1:start:3", "1:end:4", "0:end:8"]
Ожидается
[7, 2]

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