636-exclusive-time-of-functions

636. Exclusive Time of Functions (Medium) (https://leetcode.com/problems/exclusive-time-of-functions/)

На однопоточном процессоре мы выполняем программу, содержащую n функций. Каждая функция имеет уникальный ID от 0 до n - 1. Вызовы функций хранятся в стеке вызовов: когда вызов функции начинается, её ID кладётся на стек, а когда вызов завершается, ID снимается со стека. Функция, чей ID находится на вершине стека, — это функция, выполняемая в данный момент. Каждый раз, когда функция начинается или завершается, записывается лог с ID, признаком начала/завершения и меткой времени. Дан список logs, где logs[i] представляет i-й лог в формате строки “{function_id}:{“start” | “end”}:{timestamp}”. Например, “0:start:3” означает, что вызов функции с ID 0 начался в начале момента времени 3, а “1:end:2” означает, что вызов функции с ID 1 завершился в конце момента времени 2. Обратите внимание, что функция может вызываться несколько раз, в том числе рекурсивно. Эксклюзивное время функции — это сумма времени выполнения по всем вызовам этой функции в программе. Например, если функция вызвана дважды, и один вызов выполнялся 2 единицы времени, а другой — 1 единицу, то эксклюзивное время равно 2 + 1 = 3. Верните эксклюзивное время каждой функции в виде массива, где значение по индексу i представляет эксклюзивное время функции с ID i. Ограничения: - 1 <= n <= 100 - 2 <= logs.length <= 500 - 0 <= function_id < n - 0 <= timestamp <= 10^9 - Никакие два события “start” не происходят в один и тот же момент времени.

• Никакие два события “end” не происходят в один и тот же момент времени.
• Для каждого “start” лога есть соответствующий “end” лог.

function exclusiveTime(n: number, logs: string[]): number[] {
  // Стек хранит ID функций, которые сейчас "в работе" (ещё не завершились).
  // Вершина стека — текущая выполняемая функция.
  const stack: number[] = []
 
  // result[i] — суммарное эксклюзивное время функции с ID = i.
  // Эксклюзивное = только своё время, без времени дочерних вызовов.
  const result: number[] = Array.from({ length: n }, () => 0)
 
  // prevTs — timestamp предыдущего лога. Нужен, чтобы считать длительность
  // между двумя соседними событиями.
  let prevTs = 0
 
  for (let i = 0; i < logs.length; i++) {
    // Парсим лог: "function_id:start_or_end:timestamp"
    const [idStr, op, tsStr] = logs[i].split(":")
    const id = Number(idStr)
    const ts = Number(tsStr)
 
    if (op === "start") {
      // Новая функция стартует → старая функция (на вершине стека) ЗАМИРАЕТ.
      // Время от prevTs до ts принадлежит замороженной функции.
      if (stack.length > 0) {
        result[stack[stack.length - 1]] += ts - prevTs
      }
      // Кладём новую функцию на стек — теперь она текущая.
      stack.push(id)
      // Запоминаем timestamp этого события для следующей итерации.
      prevTs = ts
    } else {
      // Функция завершается. Она работала от prevTs до ts ВКЛЮЧИТЕЛЬНО.
      // +1 потому что "end:5" означает конец единицы 5 (единица 5 полностью отработана).
      result[id] += ts - prevTs + 1
      // Снимаем завершённую функцию со стека.
      stack.pop()
      // prevTs = ts + 1, а не ts, потому что единица ts уже полностью учтена этим end.
      // Следующее событие начинается с ts + 1. Если оставить prevTs = ts, то при двух
      // подряд end для одной функции (например "0:end:6" → "0:end:7") получим 7 - 6 + 1 = 2 вместо 1.
      prevTs = ts + 1
    }
  }
 
  return result
}
 
// Local check:
console.log(exclusiveTime(2, ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]))
console.log(
  exclusiveTime(1, ["0:start:0", "0:start:2", "0:end:5", "0:start:6", "0:end:6", "0:end:7"]),
)
console.log(
  exclusiveTime(2, ["0:start:0", "0:start:2", "0:end:5", "1:start:6", "1:end:6", "0:end:7"]),
)
 
// Альтернативное решение
type Status = "start" | "end"
 
interface Log {
  id: number
  status: Status
  timestamp: number
}
 
interface Call {
  id: number
  start: number
  childrenDuration: number
}
 
function exclusiveTime2(n: number, logs: string[]): number[] {
  const durations: number[] = Array.from({ length: n }, () => 0)
  const calls: Call[] = []
 
  for (let i = 0; i < logs.length; i++) {
    const log = parseLog(logs[i]!)
    const call = calls.at(-1)
 
    if (call && call.id === log.id && log.status === "end") {
      const totalDuration = log.timestamp - call.start + 1
      const selfDuration = totalDuration - call.childrenDuration
 
      const parentCall = calls.at(-2)
      if (parentCall) {
        parentCall.childrenDuration += totalDuration
      }
 
      durations[log.id]! += selfDuration
 
      calls.pop()
    } else {
      calls.push({
        id: log.id,
        start: log.timestamp,
        childrenDuration: 0,
      })
    }
  }
 
  return durations
}
 
function parseLog(log: string): Log {
  const logData = log.split(":") as [string, string, string]
  const id = Number(logData[0])
  const status = logData[1] as Status
  const timestamp = Number(logData[2])
 
  return { id, status, timestamp }
}
 
console.log(exclusiveTime2(2, ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]))
console.log(
  exclusiveTime2(1, ["0:start:0", "0:start:2", "0:end:5", "0:start:6", "0:end:6", "0:end:7"]),
)
console.log(
  exclusiveTime2(2, ["0:start:0", "0:start:2", "0:end:5", "1:start:6", "1:end:6", "0:end:7"]),
)

Пример 1:
 
    Вход: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
    Выход: [3,4]
    Объяснение:
    Функция 0 начинается в начале времени 0, затем выполняется 2 единицы времени
    и достигает конца времени 1.
    Функция 1 начинается в начале времени 2, выполняется 4 единицы времени,
    и заканчивается в конце времени 5.
    Функция 0 возобновляет выполнение в начале времени 6 и выполняется 1 единицу времени.
    Таким образом, функция 0 суммарно тратит на выполнение 2 + 1 = 3 единицы времени, а функция 1 —
    4 единицы времени.
 
Пример 2:
 
    Вход: n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"]
    Выход: [8]
    Объяснение:
    Функция 0 начинается в начале времени 0, выполняется 2 единицы времени и
    рекурсивно вызывает саму себя.
    Функция 0 (рекурсивный вызов) начинается в начале времени 2 и выполняется 4 единицы времени.
    Функция 0 (исходный вызов) возобновляет выполнение и сразу же снова вызывает саму себя.
    Функция 0 (второй рекурсивный вызов) начинается в начале времени 6 и выполняется 1 единицу времени.
    Функция 0 (исходный вызов) возобновляет выполнение в начале времени 7 и выполняется 1 единицу времени.
    Таким образом, функция 0 суммарно тратит на выполнение 2 + 4 + 1 + 1 = 8 единиц времени.
 
Пример 3:
 
    Вход: n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"]
    Выход: [7,1]
    Объяснение:
    Функция 0 начинается в начале времени 0, выполняется 2 единицы времени и
    рекурсивно вызывает саму себя.
    Функция 0 (рекурсивный вызов) начинается в начале времени 2 и выполняется 4 единицы времени.
    Функция 0 (исходный вызов) возобновляет выполнение и сразу же вызывает функцию 1.
    Функция 1 начинается в начале времени 6, выполняется 1 единицу времени и заканчивается в конце времени 6.
    Функция 0 возобновляет выполнение в начале времени 7 и выполняется 1 единицу времени.
    Таким образом, функция 0 суммарно тратит на выполнение 2 + 4 + 1 = 7 единиц времени, а функция 1 —
    1 единицу времени.

605-can-place-flowers 645-set-mismatch leetcode