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打擂台。

    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)

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;
    }
}