Merge two list ,element is a range value

Question

description:

• I need merge two lists whose element is a range value for serval (at least 10000) times efficiently. All elements should merge if they can.
• Two lists are sorted already.
• Every elements are strictly separate, it means these case are illegal:

list1 = [[1, 3], [3, 6]]
list2 = [[1, 4], [2, 5]]

list1 = [[1, 5], [6, 10]]
list2 = [[2, 4], [5, 8]]

example:

#elements: 0:start(inclusive) 1:stop(inclusive).
#the `ans` become next `list1`, to merge a new `list2` .

#input1:
list1 = [[1, 1],[3, 3]]
list2 = [[5, 5]]
#output1:
ans = [[1, 1], [3, 3], [5, 5]]

#input2:
list1 = [[1, 1], [3, 3], [5, 5]]
list2 = [[2, 2]]
#output2:
ans = [[1, 3], [5, 5]] # [1,1]+[2,2]+[3,3] = [1,3]

#input3:
list1 = [[1, 3], [5, 5]]
list2 = [[0, 0], [4, 4], [6, 6]]
#output:
ans = [[0,6]] #[0,0]+[1,3]+[4,4]+[5,5]+[6,6] = [0,6]

what I have tried:

    def merge(list1,list2):
        ans = sorted(list1+list2,key = lambda x:x[0])
        idx = 0
        while idx<len(ans):
            try:
                if ans[idx][1] == ans[idx+1][0] - 1:
                    ans[idx] = [ans[idx][0],ans[idx+1][1]]
                    del ans[idx+1]
                elif ans[idx][0] == ans[idx+1][1] + 1:
                    ans[idx] = [ans[idx+1][0],ans[idx][1]]
                    del ans[idx+1]
                else:
                    idx+=1
            except Exception:
                idx+=1
        return ans

• It works, but it is really slow. It tooks about 15 secs to solve a difficult case, 1.2 sec to solve a simple case.
• Desired time is less than 3 secs to solve a difficult case.

question

• Any better solution?
• Or which algorithm should I use? Maybe segment tree?

Answer 1

You are not using all the information. The lists are sorted already, so concatenating them and resorting is unnecessary.

def merge(list1, list2):
    # helper to process one interval from a given list
    def consume(lst, index):
        start, end = interval = lst[index]
        if not result or result[-1][-1] < start - 1:
            result.append(interval)
        elif result[-1][-1] < end:
            result[-1][-1] = end
        return index + 1

    result = []
    i1 = i2 = 0
    while i1 < len(list1) and i2 < len(list2):
        # saving some boilerplate code to always work on list1
        if list1[i1] > list2[i2]:
            list1, i1, list2, i2 = list2, i2, list1, i1
        i1 = consume(list1, i1)
    while i2 < len(list2):
        i2 = consume(list2, i2)
    return result

list1 = [[1, 1],[3, 3]]
list2 = [[5, 5]]
merge(list1, list2)
# [[1, 1], [3, 3], [5, 5]]
list1 = [[1, 1], [3, 3], [5, 5]]
list2 = [[2, 2]]
merge(list1, list2)
# [[1, 3], [5, 5]]
list1 = [[1, 3], [5, 5]]
list2 = [[0, 0], [4, 4], [6, 6]]
merge(list1, list2)
# [[0, 6]]

The algorithmic advantages of this approach seem to be outweighed by the brute C-Power of Python sorting over the context changes (particularly with the nested function). One could try to improve the solution suggested by @trincot a little though (not design-wise, but from a pure time/space-efficiency standpoint):

def merge(list1, list2):
    # sorted(l1+l2)  creates 2 new lists in memory
    list1.extend(list2)
    list1.sort()
    result = list1[:1]
    for interval in list1:
        start, end = interval
        _, e = last = result[-1]
        if e < start - 1:
            result.append(interval)
        elif e < end:  
            last[-1] = end
    return result

Answer 2

del will have an impact on performance... try to avoid it. I think it is better to let the answer list start as an empty list, and append ranges to it as you go.

Also, I don't think it is worth to provide a key argument to sorted: by default it will anyway sort by the first value in the pairs, and if there is a tie, it will sort by the second value.

Here is how it could work:

def merge(list1,list2):
    ans = []
    last = [None, -float("inf")]
    for start, end in sorted(list1+list2):
        if start > last[1] + 1:
            last = [start, end]
            ans.append(last)
        elif end > last[1]:  # Merge:
            last[1] = end  # We mutate a pair that is already in the result
    return ans