1. 057

merge-intervals/

2. 算法

http://www.cnblogs.com/grandyang/p/4367569.html

• O(n)

3. 代码

struct Interval {

    int start;

    int end;

    Interval() : start(0), end(0) {}

    Interval(int s, int e) : start(s), end(e) {}

};

class Solution{

public:

    vector<Interval>  insert(vector<Interval>& intervals,Interval newInterval){

        vector<Interval> res=intervals;

        int i=0,overlap=0,n=res.size();

        while(i<n){

            if(newInterval.end<res[i].start)  break;

            else if(newInterval.start>res[i].end) {}

            else{

                newInterval.start=min(newInterval.start,res[i].start);

                newInterval.end=max(newInterval.end,res[i].end);

                ++overlap;

            }

            ++i;

        }

        if(overlap>0)  res.erase(res.begin()+i-overlap,res.begin()+i);

        res.insert(res.begin()+i-overlap, newInterval);

        return  res;

    }

};

3.2 迭代器模式

class Solution{

public:

    vector<Interval>  insert(vector<Interval>& intervals,Interval newInterval){

        vector<Interval>  res=intervals;

        vector<Interval>::iterator it=res.begin();

        int overlap=0;



        while(it!=res.end()){

            if(newInterval.end<it->start)  break;

            else if(newInterval.start>it->end){}

            else{

                newInterval.start=min(newInterval.start,it->start);

                newInterval.end=max(newInterval.end,it->end);

                ++overlap;

            }

            ++it;

        }



        if(overlap!=0) it=res.erase(it-overlap,it);

        res.insert(it,newInterval);

        return res;

    }

};