Sort and Merge two list of lists

Question

I have two lists,

[[1, 2], [4, 7], [11, 13], [15, 21]]

[[3, 4], [5,12], [23, 25]]

I want an output like this.

[[1, 2], [3,13], [15, 21], [23, 25]]

Anybody can help me?

And how is the output determined? I fail to see the pattern. How do `[3, 4]`, `[4, 7]` and `[11, 13]` become `[3, 13]`? — Martijn Pieters, Sep 17 '12 at 10:08
can;t understand exactly how you want that ouuput? Where did the number 5, 12 go? — Shades88, Sep 17 '12 at 10:09
possible duplicate of [Merging a list of time-range tuples that have overlapping time-ranges](http://stackoverflow.com/questions/5679638/merging-a-list-of-time-range-tuples-that-have-overlapping-time-ranges); the accepted answer works perfectly for your expected output. — Martijn Pieters, Sep 17 '12 at 10:10

score 5 · Accepted Answer · edited May 23 '17 at 12:30

5

The algorithm from Merging a list of time-range tuples that have overlapping time-ranges works perfectly for your input, provided you concatenate them:

def merge(times):
    saved = list(times[0])
    for st, en in sorted([sorted(t) for t in times]):
        if st <= saved[1]:
            saved[1] = max(saved[1], en)
        else:
            yield tuple(saved)
            saved[0] = st
            saved[1] = en
    yield tuple(saved)

lst1 = [[1, 2], [4, 7], [11, 13], [15, 21]]
lst2 = [[3, 4], [5,12], [23, 25]]

print list(merge(sorted(lst1 + lst2)))

output:

[(1, 2), (3, 13), (15, 21), (23, 25)]

edited May 23 '17 at 12:30

Community

1
1

answered Sep 17 '12 at 10:14

Martijn Pieters

1,048,767
296
4,058
3,343

It does not work if `lst1` and `lst2` is swapped -- the first item has to be the "smallest" for `merge` to work correctly. – Lauritz V. Thaulow Sep 17 '12 at 11:00
@lazyr: and extra sort solves that. :-) – Martijn Pieters Sep 17 '12 at 11:05
3

+1 for guessing what the question is. – Reinstate Monica Sep 17 '12 at 11:19

Sort and Merge two list of lists

1 Answers1