# 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?

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