Merge two lists of tuples with timestamps and queue lengths

Question

The Problem: I have two lists which contain tuples (each consisting of a time stamp and a queue-length) which need to be merged:

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

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

I need a function merge(L1,L2) that returns:

[[ 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

[note: I don't need the 60+80 - it is merely to indicate which values are added the result of 60+80 = 140 is what I need]

What I extract from the output above is that I am repeatedly:

• Popping the smallest value V from the merged list of distinct timestamps (the setwise union of timestamps).
• Adding the queue-length from the non-V list of timestamps that is smaller than or equal to V.
• ...until V is exhausted.

My problem: I'm pretty sure that heapq can solve it, but can't get my head around how to structure the solution using the heapq-module.

More rambling details of the process:

1. In the first step - at 0.00 and until 7.75 the compound queue length is 50+80 - taken from L1[0][0] == L2[0][0]
2. I can add the values L1[0][1]+L2[0][1] = 50+80. I have now used L1[0][:] and L2[0][:]
3. In the second step - at 7.75 - L2's queue has not been growing, but L1's queue has: L1[1][0] = 120. To get the compound queue length in therefore need to add L1[1][1] with L2[0][1] to get 120+80.
4. I have now used the first value larger than any previously recorded and must do that for the next steps until the time intervals have been exhausted (after 23.99). The next largest value in the set of "time" is L2[1][0] which is 8.00.
5. As 8.00 is bigger than 7.75 I need to merge these values so that at 8.00 the queue length is 120+120 based on L1's largest value that is less than 8.00 - which is 7.75. Hereby I add L11 and L21.
6. In the next step the largest unused value is 10.00 from L2. The queue length from L2 needs to merge with L1 largest value, that is smaller than or equal to 10.00...
7. And so it continues...

Answer 1

Iterate over the events in the order they happen, and keep the time stamp of the last operation (last_time), so that if the next event has the same time stamp, but comes from the other queue, the two changes will be merged in one item in 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)]

Answer 2

You could also do like this :

def merge(z):
    previous=None
    l=[]
    z.sort()
    for i in range(len(z)):
        if i==len(z)-1:
            if previous==z[i][0]:
                continue
            else:
                l.append([float(z[i][0]),z[i][1])
        elif previous is None:
            previous=z[i][0]
            l.append([float(z[i][0]),z[i][1]+z[i+1][1]])
        else:
            if previous==z[i][0]:
                continue
            if z[i][0]<=z[i+1][0]:

                l.append([float(z[i][0]),z[i][1]+z[i-1][1]])
            else:
                l.append([float(z[i][0]),z[i][1]+z[i+1][1]])

    return l
L1 = [[0, 50], [7.75, 120], [10.25, 70], [17, 100], [20, 60]]
L2 = [[0, 80], [8, 120], [10, 85], [10.25, 80]]
z=L1+L2
print merge(z)

output:

[[0.0, 130], [7.75, 200], [8.0, 240], [10.0, 205], [10.25, 155], [10.25, 150], [17.0, 180], [20.0, 60]]

Answer 3

Inspired by galath's solution, I tried to find a solution for more than two inputs:

def merge(tup):
    events = list();
    i = 0 # ;-) Well, I wished I was able to compact this accumulation
    for l in tup:
        events += [(t, value, i) for (t, value) in l]
        i += 1
    events.sort(key=lambda x: x[0])
    result = dict()
    time = [0 for i in tup]
    for t, value, index in events:
        time[index] = value
        result[t] = sum(time)
    return sorted(result.items())

Tested with the original task,

L1 = [[0, 50], [7.75, 120], [10.25, 70], [17, 100], [20, 60]]
L2 = [[0, 80], [8, 120], [10, 85], [10.25, 80]]
print merge([L1, L2])

the output is the required values, as a list of tuples:

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