algorithm - [特定时间间隔内的最大能量]

Question

我遇到了一道面试题。
给定开始时间和结束时间以及在此期间传输的能量。我必须在任何瞬间找到最大能量。
例如:给定三个区间
(1,5,10)[从1开始，到5结束，此时能量为10]
(2,7,14)
(6,8,16)
然后在时间 6 到 7 之间任何时刻的最大能量是 30。
我的方法:在某种程度上这是区间重叠问题，但由于第三个参数(能量)我无法破解它。
在研究中，我认为它可以通过 Interval Tree 来解决。我正在寻找一些方法和伪代码。
谢谢!!。

Answer 1

建议的 O(nlogn) 算法:

1. 将每个 (start,end,energy) 变成 (start,energy) 和 (end,-energy) 对
2. 按第一个坐标(时间)对对排序
3. 遍历对更新当前能量并跟踪最大值

在结束时间与开始时间相符的情况下，您需要谨慎决定要做什么 - 这是否算作瞬时高能量？