algorithm - 伪代码:递归处理列表中的开始/停止时间

Question

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

我有一个脚本执行的开始/停止时间列表，其中可能包括嵌套的脚本调用。

| 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 个滴答，B 需要 4 个但执行时间仅为 3，A 需要 7 个滴答，但执行时间为 3。F 调用 G，然后调用 H，因此需要 7 个滴答，但执行时间仅为 5。

我正试图围绕我的(“流感缠身”)头脑是一个伪代码算法，用于逐步或递归遍历时间列表，以便为每一行生成时间执行值。

对于此问题(或普通感冒的治疗)的任何帮助，我们将不胜感激。 :-)

Answer 1

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

但如果您只关心执行时间，我们甚至不需要它! :) 有一个非常简单的算法，它只是对开始和结束时间进行排序，并遍历生成的“事件”数组，维护一个打开的“帧”堆栈:

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

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