寻求带权区间各时间点最小成本的最优求解算法

问题描述 #

给定一组带成本的区间（假设始终至少有一个区间处于活跃状态），需求解出一条各时间点成本均最小的非重叠区间时间线。

示例 #

输入区间列表（格式为[start, end, value]）：

[
    [2024-01-01, 2024-05-01, 500],
    [2024-01-01, 2024-03-01, 400],
    [2024-02-01, 2024-04-01, 300],
    [2024-03-01, 2024-04-01, 200]
]

对应的最优解：

[   
    [2024-01-01, 2024-02-01, 400],
    [2024-02-01, 2024-03-01, 300],
    [2024-03-01, 2024-04-01, 200],
    [2024-04-01, 2024-05-01, 500]
]

现有方案 #

• 我目前实现了扫描线算法的变体：按顺序遍历所有区间的起止点，跟踪活跃区间并选择各时间点的最小成本，时间复杂度为O(n²)，但不确定这是否是最优解。
• 补充：经@pjs提示，可通过优先队列优化选择最小成本的过程，将时间复杂度降至O(n log n)。

提问 #

是否存在其他适用于该问题的算法？我曾调研调度算法，但未找到完全适配的方案。

内容的提问来源于stack exchange，提问作者Isak