Merge Two Sorted Interval Lists

• Lintcode : 839 / Leetcode :
• Level : Easy

Problem

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.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n)
space: O(1)

Answer

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

class Solution {
public:
    vector<Interval> mergeTwoInterval(vector<Interval> &list1, vector<Interval> &list2) {
        vector<Interval> ans;
        int i = 0, j = 0;
        int len1 = list1.size(), len2 = list2.size();
        while (i < len1 && j < len2) {
            while (i < len1 && j < len2 && list1[i].start <= list2[j].start) {
                if (ans.size() > 0 && list1[i].start <= ans[ans.size() - 1].end) {
                    ans[ans.size() - 1].end = max(list1[i].end, ans[ans.size() - 1].end);
                }else {
                    ans.push_back(list1[i]);
                }
                i++;
            }
            while (i < len1 && j < len2 && list1[i].start > list2[j].start) {
                if (ans.size() > 0 && list2[j].start <= ans[ans.size() - 1].end) {
                    ans[ans.size() - 1].end = max(list2[j].end, ans[ans.size() - 1].end);
                }else {
                    ans.push_back(list2[j]);
                }
                j++;
            }
        }
        while (i < len1) {
            if (ans.size() > 0 && list1[i].start <= ans[ans.size() - 1].end) {
                ans[ans.size() - 1].end = max(list1[i].end, ans[ans.size() - 1].end);
            }else {
                ans.push_back(list1[i]);
            }
            i++;
        }
        while (j < len2) {
            if (ans.size() > 0 && list2[j].start <= ans[ans.size() - 1].end) {
                ans[ans.size() - 1].end = max(list2[j].end, ans[ans.size() - 1].end);
            }else {
                ans.push_back(list2[j]);
            }
            j++;
        }
        return ans;
    }
};

tags: 2pointers

​