Lintcode 839. Merge Two Sorted Interval Lists

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.

Example

Example1

Input: list1 = [(1,2),(3,4)] and list2 = [(2,3),(5,6)]
Output: [(1,4),(5,6)]
Explanation:
(1,2),(2,3),(3,4) --> (1,4)
(5,6) --> (5,6)

Example2

Input: list1 = [(1,2),(3,4)] and list2 = [(4,5),(6,7)]
Output: [(1,2),(3,5),(6,7)]
Explanation:
(1,2) --> (1,2)
(3,4),(4,5) --> (3,5)
(6,7) --> (6,7)

Notice

• The intervals in the given list do not overlap.
• The intervals in different lists may overlap.

Code (Java):

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

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) {
        // write your code here
        List<Interval> ans = new ArrayList<>();
        int i = 0;
        int j = 0;

        Interval prev = null;

        while (i < list1.size() && j < list2.size()) {
            Interval curr = null;
            Interval v1 = list1.get(i);
            Interval v2 = list2.get(j);
            if (v1.start < v2.start) {
                curr = v1;
                i++;
            } else {
                curr = v2;
                j++;
            }

            prev = merge(ans, prev, curr);
        }

        while (i < list1.size()) {
            Interval curr = list1.get(i);
            prev = merge(ans, prev, curr);
            i++;
        }

        while (j < list2.size()) {
            Interval curr = list2.get(j);
            prev = merge(ans, prev, curr);
            j++;
        }

        if (prev != null) {
            ans.add(prev);
        }

        return ans;
    }

    private Interval merge(List<Interval> ans, Interval prev, Interval curr) {
        if (prev == null) {
            return curr;
        }

        if (prev.end < curr.start) {
            ans.add(prev);
            prev = curr;
            return prev;
        }

        prev.end = Math.max(prev.end, curr.end);

        return prev;
    }
}

Update on 4/23/20:

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

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) {
        // write your code here
        List<Interval> ans = new ArrayList<>();
        
        if (list1 == null || list1.size() == 0) {
            return list2;
        } 
        
        if (list2 == null || list2.size() == 0) {
            return list1;
        }
        
        Interval prev = null;
        
        int i = 0;
        int j = 0;
        
        while (i < list1.size() || j < list2.size()) {
            if (i == list1.size()) {
                prev = merge(prev, list2.get(j), ans);
                j++;
            } else if (j == list2.size()) {
                prev = merge(prev, list1.get(i), ans);
                i++;
            } else if (list1.get(i).start < list2.get(j).start) {
                prev = merge(prev, list1.get(i), ans);
                i++;
            } else {
                prev = merge(prev, list2.get(j), ans);
                j++;
            }
        }
        
        ans.add(prev);
        
        return ans;
    }
    
    private Interval merge(Interval prev, Interval curr, List<Interval> ans) {
        if (prev == null) {
            prev = curr;
        } else if (!isOverlapped(prev, curr)) {
            ans.add(new Interval(prev.start, prev.end));
            prev = curr;
        } else {
            prev.start = Math.min(prev.start, curr.start);
            prev.end = Math.max(prev.end, curr.end);
        }
        
        return prev;
    }
    
    private boolean isOverlapped(Interval a, Interval b) {
        return a.end >= b.start;
    }
}