LeetCode 1661. 每台机器的进程平均运行时间
题目描述
题意分析
Activity记录每台机器各个进程的开始、结束事件。每个进程的运行时间是结束时间减开始时间，要求按机器计算这些运行时间的平均值，保留三位小数，输出machine_id和processing_time。
解法：SQL 自连接 + 分组平均
核心思路
[!blue]
同一张表分别取别名
s、e，让s只代表开始事件，e只代表结束事件。连接时同时要求machine_id和process_id相同，才能把同一台机器上同一个进程的两条记录配成一对。题目保证每个进程恰有对应的开始与结束记录，因此这样的连接结果中，每个进程正好出现一行。这一行的
e.timestamp - s.timestamp就是完整运行时间，既不会混入其他机器的同编号进程，也不会把开始事件与自身配对。在配对结果上只按机器编号分组，
AVG统计组内所有进程耗时的平均值。最后对这个平均值执行ROUND(..., 3)，得到题目要求的精度；不能先把每个进程耗时舍入，再计算平均，否则可能改变最终结果。
解题步骤
- 将
Activity自连接，分别限制s.activity_type = 'start'、e.activity_type = 'end'。- 用机器编号与进程编号共同匹配两侧记录。
- 对每个配对行计算结束时间减开始时间。
- 仅按
s.machine_id分组，对耗时取平均后保留三位小数，使用processing_time作为结果列名。
代码实现
SELECT
s.machine_id,
ROUND(AVG(e.timestamp - s.timestamp), 3) AS processing_time
FROM Activity s
JOIN Activity e
-- 机器与进程编号共同配对，保证每行表示同一进程的开始和结束。
ON e.machine_id = s.machine_id
AND e.process_id = s.process_id
AND s.activity_type = 'start'
AND e.activity_type = 'end'
GROUP BY s.machine_id;
复杂度分析
设原表有
n条事件记录。正确配对后每个进程只生成一行，因此连接结果与输入规模同阶。
- 时间复杂度：取决于连接和聚合执行计划；采用哈希连接与哈希聚合时可按期望 $O(n)$ 估算，索引连接或嵌套循环可能有不同成本。
- 空间复杂度：取决于数据库工作区；哈希执行方式通常需要 $O(n)$ 空间保存连接或聚合状态。
关键点总结
[!green]
- 自连接先把两条事件变成一条进程记录，再对进程耗时求平均。
- 完整连接键由机器和进程编号共同组成，事件类型分别固定为开始和结束。
- 分组维度决定输出粒度，只按机器分组才会得到每台机器一行。
易错点总结
[!yellow]
- 只按进程编号连接，会把不同机器上的同编号进程混配。
- 漏掉某侧事件类型限制，可能产生同类事件配对或重复配对。
- 减法方向必须是结束减开始，反过来会得到负运行时间。
- 同时按机器和进程分组，会返回每个进程的耗时，无法得到机器平均值。
- 保留三位小数应作用于平均结果，不要提前舍入每个进程耗时。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1396. 设计地铁系统 | 中等 | 同样先配对开始结束事件求持续时间，再按机器或路线汇总总时长和次数求平均。 |
| 175. 组合两个表 | 简单 | 关联键必须同时定位同一机器和进程的开始结束记录，不能只按时间或单个ID随意连接。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！