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

Question

问题: 我有两个包含需要合并的元组(每个由时间戳和队列长度组成)的列表:

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 union timestamps).
• V从小于或等于的非时间戳列表中添加队列长度V.
• ......直到V筋疲力尽.

我的问题: 我很确定heapq可以解决它,但无法理解如何使用heapq-module构建解决方案.

更多漫无边际的细节:

1. 在第一步 - 从0.00到7.75,复合队列长度50+80- 取自L1[0][0] == L2[0][0]
2. 我可以添加值L1[0][1]+L2[0][1] = 50+80.我现在用过L1[0][:]和L2[0][:]
3. 在第二步 - 在7.75 - L2的队列没有增长,但L1的队列有:L1[1][0] = 120.为了获得该化合物队列长度,因此需要加L1[1][1]用L2[0][1]得到120+80.
4. 我现在使用的第一个值大于以前记录的任何值,必须在接下来的步骤中使用,直到时间间隔用尽(23.99之后)."时间"集合中的下一个最大值L2[1][0]是8.00.
5. 当8.00大于7.75时,我需要合并这些值,以便在8.00时队列长度为120 + 120,基于L1的最大值小于8.00 - 即7.75.在此我添加L1 1和L2 1.
6. 在下一步中,最大的未使用值是来自L2的10.00.L2需要合并的队列长度L1最大值,小于或等于10.00 ...
7. 所以它继续......

Answer 1

按照事件发生的顺序迭代事件，并保留上次操作的时间戳（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)]