> For the complete documentation index, see [llms.txt](https://loghead.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://loghead.gitbook.io/algorithm-notes/array-matrix-interval-binary-indexed-tree/merge-two-sorted-interval-lists.md).

# Merge Two Sorted Interval Lists

LintCode 839

> Merge two sorted (ascending) lists of interval and return it as a new sorted list. The new sorted list should be made by splicing together the intervals of the two lists and sorted in ascending order.
>
> ## Notice
>
> * The intervals in the given list do not overlap.
> * The intervals in different lists may overlap.
>
> **Example**
>
> Given list1 =`[(1,2),(3,4)]`and list2 =`[(2,3),(5,6)]`, return`[(1,4),(5,6)]`.

合并 interval 的思路和上一题一样。合并2个 interval lists 可以套用合并2个sorted array的方法，两个list打擂台。

```python
    def mergeTwoInterval(self, list1, list2):
        if not list1 or not list2:
            return list1 + list2

        lo = hi = min(list1[0].start, list2[0].start)
        i, j, result = 0, 0, []
        while i < len(list1) or j < len(list2):
            if i == len(list1):
                interval = list2[j]
                j += 1
            elif j == len(list2):
                interval = list1[i]
                i += 1                
            elif list1[i].start < list2[j].start:
                interval = list1[i]
                i += 1
            else:
                interval = list2[j]
                j += 1

            if interval.start > hi:
                result.append(Interval(lo, hi))
                lo, hi = interval.start, interval.end
            else:
                hi = max(hi, interval.end)

        result.append(Interval(lo, hi))

        return result[: ]
```

九章的思路

> 用一个 last 来记录最后一个还没有被放到 merge results 里的 Interval，用于和新加入的 interval 比较看看能不能合并到一起。
>
> 时间复杂度O(n + m)O(n+m)
>
> ```java
> public class Solution {
>     /**
>      * @param list1: one of the given list
>      * @param list2: another list
>      * @return: the new sorted list of interval
>      */
>     public List<Interval> mergeTwoInterval(List<Interval> list1, List<Interval> list2) {
>         List<Interval> results = new ArrayList<>();
>         if (list1 == null || list2 == null) {
>             return results;
>         }
>         
>         Interval last = null, curt = null;
>         int i = 0, j = 0;
>         while (i < list1.size() && j < list2.size()) {
>             if (list1.get(i).start < list2.get(j).start) {
>                 curt = list1.get(i);
>                 i++;
>             } else {
>                 curt = list2.get(j);
>                 j++;
>             }
>             
>             last = merge(results, last, curt);
>         }
>         
>         while (i < list1.size()) {
>             last = merge(results, last, list1.get(i));
>             i++;
>         }
>         
>         while (j < list2.size()) {
>             last = merge(results, last, list2.get(j));
>             j++;
>         }
>         
>         if (last != null) {
>             results.add(last);
>         }
>         return results;
>     }
>     
>     private Interval merge(List<Interval> results, Interval last, Interval curt) {
>         if (last == null) {
>             return curt;
>         }
>         
>         if (curt.start > last.end) {
>             results.add(last);
>             return curt;
>         }
>         
>         last.end = Math.max(last.end, curt.end);
>         return last;
>     }
> }
> ```