636. Exclusive Time of Functions

2020-04-19 本文已影响0人微微笑的蜗牛

@(LeetCode)

问题描述

我们将在一个单线程 cpu 上执行一些函数。每个函数有个唯一 id, 范围是 [0, N-1]。

我们按时间顺序存储日志，这些日志描述了函数进入或退出的时机。

每个日志是个字符串，其格式为：{function_id}:{"start" | "end"}:{timestamp}。

举个栗子，"0:start:3" 表示函数 0 在时间戳为 3 时启动。"1:end:2" 表示函数 1 在时间戳为 2 的时候停止。

一个函数的独占执行时间是指在该函数上花费的时间片。注意函数没有递归调用或者调用子函数。

CPU 是单线程的，意味着在一个时间片中只能执行一个函数。

要求按照函数 id 顺序，返回每个函数的独占执行时间。

栗 1：

WX20200419-143646@2x.png

输入：
n = 2
logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]

输出：[3, 4]
解释：
函数 0 在 0 时启动，它会执行 2 个时间片；
函数 1 在 2 时启动，在 5 时结束，执行了 4 个时间片；
函数 0 在 6 时结束，执行了 1 个时间片。
因此，函数 0 总共执行时间为 2 + 1 = 3，函数 1 的时间为 4。

注意：

1 <= n <= 100。
两个函数不会在相同的时间点开始或结束。
当函数退出时，也会打印日志。

想看英文原文的戳这里。

解题思路

首先梳理一下题意：

日志是按时间顺序存储的。
start、end 代表了函数的开始和结束。
由于是单线程，所以 end 的函数一定是前一个 start 的函数。
如果 cpu 空闲了，前一个被挂起的函数会执行。
按函数 id 大小返回结果。
这里有个小技巧。由于至多只有 0 <= n <= 100 个函数，完全可以初始化一个有 n 个元素的数组，且值都为 0。之后直接根据函数 id 填值即可。

另外还有重要的一点：

同一个函数可能被 start 多次。

这是我在提交代码出错后，看它的测试用例才知道。此时才发现原来我的解法完全的错了。

初始想法

由于没有考虑到一个函数会被 start 多次，因此按照常规的思路，将每个函数执行的开始/结束时间存下来，然后判断是否在其他函数执行时间段内，来计算真正的执行时间。

但提交代码时，傻眼了，原来还有多次 start 的情况。那么这种解法完全不行。

正确思路

由于日志是按时间顺序排列的，那么我们按照这个顺序去遍历就好。

但是遍历时，前后函数 log 可能存在的情况较多，假设前一个函数的时间戳为 t1，后一个函数的时间戳为 t2。具体情况如下：

start-start
在这种情况下，又分为同一个函数和不同的函数。
1. 对于同一个函数 0：["0:start:0","0:start:2",...]，此时函数 0 的执行时间为： 2-0=2。
2. 对于不同的函数：["0:start:0","1:start:2",...]，此时也还是函数 0 的执行时间： 2。
因此，对于同一个函数或者不同函数来说，其计算方法都一样。通用计算公式为：t=t2-t1。
end-end
1. 对于同一个函数：[...,"1:end:5","1:end:6"]，此时函数 1 的执行时间为：6-5=1。
2. 对于不同的函数：[...,"1:end:5","0:end:6"]，此时函数 0 的执行时间为：6-5=1。
与上面 start-start 的情况类似，t=t2-t1。
start-end
这种情况下，前后函数 id 一定是匹配的。

比如：["1:start:2","1:end:5",...]。

因此函数 1 的执行时间为：5-2+1=4。通用计算公式为：t=t2-t1+1。
end-start

这种情况表示：一个函数结束，另一个函数开始。这中间可能会有段空闲时间，可用于执行前一个挂起的函数。

举个栗子：
```
logs = ["0:start:0","1:start:3","1:end:5","0:start:8",...]
```
- 函数 0 在 0 时开始，函数 1 在 3 时开始，此时函数 0 挂起；
- 函数 1 在 5 时结束；
- 函数 0 在 8 时开始。
因此，这中间会有 8-5-1=2 个空闲的时间片，供前一个挂起的函数 0 来执行。通用计算公式为：t=t2-t1-1。

所以在这种情况下，我们需要记录之前未结束的函数 id，当有空闲时间片时，取出最近的一个函数来执行。

通过分析上述情形，我们可以得出：

start-start 和 end-end 是同一种处理方式，t=t2-t1。
start-end 是一次开始和结束的完整过程，t=t2-t1+1。
end-start，中间的空闲时间片可以执行挂起的函数，t=t2-t1-1。
需要用队列/栈记录未结束的函数 id。在 start 时记录，在 end 时删除。

按照各种不同的情况，将对应函数的执行时间片进行累加即可。

完整代码可点此查看。

case 简化

以上分析的各种情形有点复杂，其实并不用细化到那么多场景。只需要判断当前的日志是 start 还是 end 即可。

若当前日志是 start，则：

// curTime 表示当前日志的时间戳
// preTime 表示之前的时间戳
t = curTime - preTime
preTime = curTime

若当前日志是 end，则

// curTime 表示当前日志的时间戳
// preTime 表示之前的时间戳
t = curTime - preTime + 1

// 注意，这里需要 + 1。因为如果当前时间戳为 5，下一个日志为 start 且时间戳为 6，那么计算出的时间应该为 0，所以要 +1。
preTime = curTime + 1

python 代码如下：

def exclusiveTime(self, N, logs):
    ans = [0] * N
    stack = []
    prev_time = 0

    for log in logs:
        fn, typ, time = log.split(':')
        fn, time = int(fn), int(time)

        if typ == 'start':
            if stack:
                ans[stack[-1]] += time - prev_time 
            stack.append(fn)
            prev_time = time
        else:
            ans[stack.pop()] += time - prev_time + 1
            prev_time = time + 1

    return ans

具体代码可点此查看。