Merge two list ,element is a range value

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

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