伪代码：在列表中递归处理 start/stop 次

Question

这是一个相当模糊的问题。

我有一份脚本执行 start/stop 次的列表，其中可能包括嵌套的脚本调用。

| script | start | stop |    duration    |            time executing           |
| ------ | ----- | ---- | -------------- | ----------------------------------- |
| A      |     1 |    8 | 7 i.e. (8-1)   | 3 i.e. ((8-1) - (6-2) - (5-4))      |
| ->B    |     2 |    6 | 4 i.e. (6-2)   | 3 i.e. ((6-2) - (5-4))              |
| ->->C  |     4 |    5 | 1 i.e. (5-4)   | 1                                   |
| D      |     9 |   10 | 1 i.e. (10-9)  | 1                                   |
| E      |    11 |   12 | 1 i.e. (12-11) | 1                                   |
| F      |     9 |   16 | 7 i.e. (16-9)  | 5 i.e. ((16-9) - (14-13) - (16-15)) |
| ->G    |    13 |   14 | 4 i.e. (14-13) | 1 i.e. (14-13)                      |
| ->H    |    15 |   16 | 1 i.e. (15-14) | 1 i.e. (16-15)                      |

持续时间是在脚本中花费的总时间。执行时间是在脚本中花费的时间，而不是在下标中。

所以A调用B，B调用C。C需要1个tick，B需要4个，但是执行时间只有3个，A需要7个tick，但是执行时间是3个。 F 调用 G，然后调用 H，因此需要 7 个滴答，但执行时间仅为 5.

我试图解决我的（“流感缠身”）问题是一种伪代码算法，用于逐步或递归时间列表，以便为每一行生成时间执行值。

对于这个问题（或治疗普通感冒）的任何帮助，我们都感激不尽。 :-)

Answer 1

如果所有时间点都不同，则脚本执行时间跨度通过有序树相互关联：给定任何一对脚本执行时间跨度，其中一个严格包含另一个，或者它们根本不重叠。如果您想这样做，这可以轻松恢复亲子关系。

但如果您只关心执行时间，我们甚至不需要！ :) 有一个非常简单的算法，它只是对开始时间和结束时间进行排序，然后遍历 "events" 的结果数组，维护一个打开的 "frames":

的堆栈

创建一个包含 (time, scriptID) 对的数组，并将每个脚本的开始时间和结束时间插入其中（即，将每个脚本两对插入同一数组）。
按时间对数组进行排序。
创建一堆整数三元组，并在其上推送一个 (0, 0, 0) 条目。（这只是一个虚拟条目，以简化后面的代码。）同时创建一个数组 seen[]，每个脚本 ID 都有一个布尔标志，所有初始设置为 false.
遍历 (time, scriptID) 对的排序数组：
- 每当您看到一个您以前从未见过的脚本 ID 的 (time, scriptID) 对时，该脚本就会启动。
  - 设置seen[scriptID] = true.
  - 将三元组 (time, scriptID, 0) 压入堆栈。最后一个组件，最初为 0，将用于累积在此脚本的 "descendant" 个脚本中花费的总持续时间。
- 每当您看到之前看到的脚本 ID 的时间（因为 seen[scriptID] == true），该脚本就结束了。
  - 从堆栈中弹出顶部 (time, scriptID, descendantDuration) 三元组（请注意，此三元组中的 scriptID 应与数组当前索引处的对中的 scriptID 匹配；如果不是，那么不知何故你有 "intersecting" 无法对应于任何嵌套脚本运行序列的脚本时间跨度）。
  - 此脚本 ID 的持续时间是（如您所知）time - startTime[scriptID]。
  - 它的执行时间是duration - descendantDuration。
  - 通过将其 duration 添加到新的栈顶 descendantDuration（即第三个) 字段。

就是这样！对于 n 个脚本执行，这将花费 O(n log n) 时间，因为排序步骤需要这么长时间（遍历数组并执行堆栈操作只需要 O(n)）。 Space 用法是 O(n)。

伪代码：在列表中递归处理 start/stop 次

Pseudocode: Recursively process start/stop times in list

algorithm

recursion

profiling

pseudocode