Day 1: Lintcode【区间】【简单】【合并区间*2】

一.
描述

Given a collection of intervals, merge all overlapping intervals.
样例
Example 1:
Input: [(1,3)]
Output: [(1,3)]

Example 2:
Input: [(1,3),(2,6),(8,10),(15,18)]
Output: [(1,6),(8,10),(15,18)]

挑战
O(n log n) time and O(1) extra space.

	/**
	 * Definition of Interval:
	 * classs Interval {
	 *     int start, end;
	 *     Interval(int start, int end) {
	 *         this->start = start;
	 *         this->end = end;
	 *     }
	 * }
	 */
	
	class Solution {
	public:
	    static bool cmp(const Interval &a, const Interval &b){
	        return a.start<b.start;
	    }
	    /**
	     * @param intervals: interval list.
	     * @return: A new interval list.
	     */
	    vector<Interval> merge(vector<Interval> &intervals) {
	        // write your code here
	        int n = intervals.size();
	        vector <Interval> result;
	        if(n<=1) return intervals;
	        
	        sort(intervals.begin(),intervals.end(),cmp);
	        int left = intervals[0].start;
	        int right = intervals[0].end;
	
	        for(int i=0; i<n; ++i){
	            if(intervals[i].start<=right){
	                right=max(right, intervals[i].end);
	            }
	            else{
	                result.push_back(Interval(left, right));
	                left = intervals[i].start;
	                right = intervals[i].end;
	            }
	        }
	        result.push_back(Interval(left,right));
	        return result;
	    }
	};

(思路借鉴brucehb大佬的~)

二.
描述
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.

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

样例
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)

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

class Solution {
public:
    /**
     * @param list1: one of the given list
     * @param list2: another list
     * @return: the new sorted list of interval
     */
    static bool cmp(const Interval &a, const Interval &b){
        return a.start<b.start;
    }
    vector<Interval> mergeTwoInterval(vector<Interval> &list1, vector<Interval> &list2) {
        // write your code here
        vector <Interval> merge, result;
        int n1 = list1.size();
        int n2 = list2.size();
        for(int i=0; i<n1; ++i){
            merge.push_back(list1[i]);
        }
        for(int i=0; i<n2; ++i){
            merge.push_back(list2[i]);
        }
        sort(merge.begin(),merge.end(),cmp);
        int n3= n1+n2;
        if(n3<=1) return merge;
        int left = merge[0].start, right = merge[0].end;
        for(int i=0; i<n3; ++i){
            if(merge[i].start<=right){
                right = max(right, merge[i].end);
            }
            else{
                result.push_back(Interval(left, right));   
                left = merge[i].start; right = merge[i].end;
            }
        }
        result.push_back(Interval(left, right));
        return result;
    }
};