合并两个带有时间戳和队列长度的元组列表

根11

问题：我有两个列表，其中包含需要合并的元组（每个元组包含一个时间戳和一个队列长度）：

L1 = [[0, 50], [7.75, 120], [10.25, 70], [17, 100], [20, 60]]

L2 = [[0, 80], [8, 120], [10, 85], [10.25, 80]]

我需要一个merge(L1,L2)返回的函数：

[[ 0.00,  50+80 ],
 [ 7.75, 120+80 ],
 [ 8.00, 120+120],
 [10.00,  85+120],
 [10.25,  70+80 ],
 [17.00, 100+80 ],
 [20.00,  60+80 ]] # note

[注意：我不需要60+80-只是指示要添加哪些值，60+80=的结果140就是我需要的]

我从上面的输出中提取的是我反复：

V从不同时间戳的合并列表中弹出最小值（的setwise并集timestamps）。
从非V时间戳列表中添加小于或等于的队列长度V。
...直到V筋疲力尽。

我的问题：我很确定heapq可以解决它，但是我无法理解如何使用heapq模块构造解决方案。

该过程的更多细节：

第一步-从0.00开始直到7.75，复合队列长度50+80取自L1[0][0] == L2[0][0]
我可以添加值L1[0][1]+L2[0][1] = 50+80。现在我已经使用L1[0][:]和L2[0][:]
第二步-在7.75-L2的队列没有增长，但是L1的队列有：L1[1][0] = 120。为了获得该化合物队列长度，因此需要加L1[1][1]用L2[0][1]得到120+80。
我现在使用的第一个值大于以前记录的任何值，并且必须在接下来的步骤中使用该值，直到用尽时间间隔（在23.99之后）。“时间”集中的下一个最大值L2[1][0]是8.00。
因为8.00大于7.75，所以我需要合并这些值，以便在8.00时，基于L1的最大值小于8.00的队列长度为120 + 120，也就是7.75。因此，我添加了L1 1和L2 1。
在下一步中，最大的未使用值是L2中的10.00。L2需要合并的队列长度为L1最大值，该值小于或等于10.00 ...
所以它继续...

疾病

按照事件发生的顺序迭代事件，并保留上一个操作（last_time）的时间戳，以便如果下一个事件具有相同的时间戳，但来自另一个队列，则两个更改将合并到一个项目中在中result。

def merge(a, b):
    l1 = [(t, value, 1) for (t, value) in a]
    l2 = [(t, value, 2) for (t, value) in b]
    events = l1 + l2
    events.sort()
    last_time = -1
    result = []
    c1 = 0
    c2 = 0
    for t, value, index in events:
        if index == 1: 
            c1 = value
        if index == 2: 
            c2 = value
        if t == last_time:
            result.pop()
        result.append((t, c1 + c2))
        last_time = t
    return result

In [26]: L1 = [[0, 50], [7.75, 120], [10.25, 70], [17, 100], [20, 60]]
         L2 = [[0, 80], [8, 120], [10, 85], [10.25, 80]]

         merge(L1, L2)

Out[26]: [(0, 130), (7.75, 200), (8, 240), (10, 205), (10.25, 150), (17, 180), (20, 140)]

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。