Эксклюзивное время исполнения функций

Источник: https://leetcode.com/problems/exclusive-time-of-functions/

На однопотоково процессоре исполняется программа из n функций. У каждой функции есть уникальный ID между 0 и n-1.

Вызовы функций хрнаятся в стеке: ID функции заносится в стек в начале исполнения функции и удаляется из него в конке исполнения функции. Функция, чей ID в верхушке стека - исполняющаяся в текущий момент функция. Каждый раз, когда функция начинается и заканчивается, мы пишем лог с ID, начало или конец исполнения, таймстемп.

Дон список логов logs, где logs[i] предсталяет собой i-е сообщение лога в формате: "{function_id}:{"start" | "end"}:{timestamp}". Например,
"0:start:3" означает, что функция с ID=0 стартовала в момент времени, кjгда timestamp=3,
"1:end:2" функция с ID=1 закончилась в момент времени timestamp=2. 

Функиця может быть вызвана много раз, в том числе и рекурсивно.

Эксклюзивное время фукнции - это сумма всех интервалов исполнения. Например, если функция была вызвана 2 раза, и первый раз она исполнялась две единицы времени, а второй раз исполнялась одну единицу времени, то ее эксклюзивное время исполнения - это 2 + 1 = 3.

Вернуть эксклюивзное время исполнения всех функций в массиве, где i-й  элемент массива содержит эфксклюзивное время исполнения функции с ID=i.

Пример 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.
Итого функция 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 и заканчивается в 5 => итого занимает 2, 3, 4, 5, то есть 4 единицы времени
Ф 0 (исзодный вызов) возвращается к исполнению после 5 и заканчивается в 6.
Ф 0 (второй рекурсивный вызов) начинается в 6 и заканчивается в 6 (то есть занимает 1 единицу времени).
Ф 0 (исходный вызывов) возобновляет работу после 6 и заканчивает в 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]

Пример 4:

Дано: n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:7","1:end:7","0:end:8"]
Результат: [8,1]

Пример 5:

Дано: n = 1, logs = ["0:start:0","0:end:0"]
Результат: [1]

Ограничения:

• 1 <= n <= 100
• 1 <= logs.length <= 500
• 0 <= function_id < n
• 0 <= timestamp <= 109
• В ту же самую единицу времени стартует или заканчивается максимум 1 функция.
• У каждой функции есть "end" для каждого ее "start" в логах.

Идея решения

Если представить start, как открывающуюю скобку, а end - как закрывающую скобку в выражении, то для обработки выражения со скобками мы обычно используем стек. Заносим в стек новый элемент каждый раз, как стречаем открывающую скобку, и достаем - при встрече  открывающей скобкой.

В данной задаче мы ещё параллельно и подсчиитываем длительность интервалов между скобками.

1. () end-start+1 = длительность процесса между start и end;
2. (( start2-start1 = длительность (части) процесса 1, который прерывется процессом 2 в start 2;
   
3. )) end1-end2 = длительность части процесса 1, который возобновился после процесса 2 в end2;
4. )( start3-end2 = длительность части процесса 2, который возобновил работу после того, как закончиося процесс 2 в end2 и до того, как начался процесс 3 в start 3.
   

Имплементация 

class Solution {
    public int[] exclusiveTime(int n, List <String> logs) {
        Stack <Integer> stack = new Stack <> ();
        int[] res = new int[n];
        // обработаем первый лог
        String[] s = logs.get(0).split(":");
        stack.push(Integer.parseInt(s[0]));
        int i = 1, prev = Integer.parseInt(s[2]); // кейс 2
        //  в prev мы храним время предыдущей опорной точки (start или end)
        // теперь рассматриваем другие записи лога
        while (i < logs.size()) {
            s = logs.get(i).split(":");
            if (s[1].equals("start")) { // кейсы 2 или 4
                // все старты заносим в стек
                if (!stack.isEmpty()) {
                    // обновляем длительность предыдущего процесса,
                    // поскольку новый старт прерывает его
                    // stack.peek() - это ID предыдущего процесса
                    // res[stack.peek()] аккумулирует эксклюзивное время процесса
                    res[stack.peek()] += Integer.parseInt(s[2]) - prev;
                }
                // заносим стек новый процесс processId
                stack.push(Integer.parseInt(s[0]));
                // запоминаем начальную координату отрезка
                prev = Integer.parseInt(s[2]); // ВКЛЮЧАЕМ
                //в следующий интервал точку завершения текущего отрезка

            } else { // кейсы 1 или 3
                // достаем элемент из стека
                res[stack.peek()] += Integer.parseInt(s[2]) - prev + 1;
                stack.pop();
                // запоминаем следующую координту старта
                prev = Integer.parseInt(s[2]) + 1; // НЕ ВКЛЮЧАЕМ
                //в следующий интервал точку завершения текущего отрезка
                // за счет этого кейс 4 получается start3-end2 без +1
            }
            i++;
        }
        return res;
    }
}