Merge Two Interval Lists

https://discuss.leetcode.com/topic/245/merge-two-interval-lists?page=1

Given A and B two interval lists, A has no overlap inside A and B has no overlap inside B. Write the function to merge two interval lists, output the result with no overlap. Ask for a very efficient solution

A naive method can combine the two list, and sort and apply merge interval in the leetcode, but is not efficient enough.

For example, A: [1,5], [10,14], [16,18] B: [2,6], [8,10], [11,20]

output [1,6], [8, 20]

Thoughts

和merge 2 sorted list很像, 只是merge时要用merger interval的思路.

Code

import java.util.*;

public class Solution {
    public Solution() {
        List<Interval> intervals1 = new ArrayList<>(), intervals2 = new ArrayList<>();
        intervals1.add(new Interval(1, 5));
        intervals1.add(new Interval(10, 14));
        intervals1.add(new Interval(16, 18));

        intervals2.add(new Interval(2, 6));
        intervals2.add(new Interval(8, 10));
        intervals2.add(new Interval(11, 20));

        List<Interval> res = merge(intervals1, intervals2);
        for (Interval interval : res) {
            System.out.println(interval.start + "," + interval.end);
        }
    }


    public class Interval {
        int start;
        int end;
        Interval() { start = 0; end = 0; }
        Interval(int s, int e) { start = s; end = e; }
    }

    public void merge(List<Interval> res, Interval interval) {
        if (res.size() > 0 && interval.end <= res.get(res.size() - 1).end) {
            return;
        }
        if (res.size() > 0 && interval.start <= res.get(res.size() - 1).end) {
            res.get(res.size() - 1).end = interval.end;
        } else {
            res.add(new Interval(interval.start, interval.end));
        }
    }

    public List<Interval> merge(List<Interval> intervals1, List<Interval> intervals2) {
        List<Interval> res = new ArrayList<>();
        int m = intervals1.size(), n = intervals2.size();
        if (m == 0 && n == 0) {
            return res;
        }
        intervals1.sort((a, b) -> a.start - b.start);
        intervals2.sort((a, b) -> a.start - b.start);
        int start = 0, end = 0;
        for (int l = 0, r = 0; l < m || r < n;) {
            if (l == m) {
                merge(res, intervals2.get(r));
                r++;
            } else if (r == n) {
                merge(res, intervals1.get(1));
                l++;
            } else {
                if (intervals1.get(l).start <= intervals2.get(r).start) {
                    merge(res, intervals1.get(l));
                    l++;
                } else {
                    merge(res, intervals2.get(r));
                    r++;
                }
            }
        }

        return res;
    }


    public static void main(String args[]) {
        /*
        For example,
        A: [1,5], [10,14], [16,18]
        B: [2,6], [8,10], [11,20]

        output [1,6], [8, 20] */

        Solution solution = new Solution();

    }
}

Analysis

排序耗时O(NlgN + MlgM), 如果Input排好序的话则是O(m + n).