学步园

Merge Intervals:

Given a collection of intervals, merge all overlapping intervals.

For example,

Given [1,3],[2,6],[8,10],[15,18],

return [1,6],[8,10],[15,18].

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
 
class Interval_cmp:binary_function<Interval,Interval,bool>
{
public:
    bool operator()(const Interval& i1,const Interval& i2)
	{
		if ( i1.start==i2.start )
			return i1.end<i2.end;
		return i1.start<i2.start;
	}
};

class Solution {
public:
    vector<Interval> merge(vector<Interval> &inters) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int n =inters.size();
	    if (n<=1 )
		    return inters;
	    sort(inters.begin(),inters.end(),Interval_cmp());
	    int start=inters[0].start,end=inters[0].end;
	    vector<Interval> ret;
	    for(int i=1;i<n;i++)
	    {
		    if ( end < inters[i].start )
		    {
			    ret.push_back(Interval(start,end));
			    start=inters[i].start;
			    end=inters[i].end;
		    }
		    else
		    {
			    end=max(end,inters[i].end);
		    }
	    }
	    ret.push_back(Interval(start,end));
	    return ret;
    }
};

Insert Interval：

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Given intervals [1,3],[6,9],
insert and merge [2,5] in
as [1,5],[6,9].

Example 2:

Given [1,2],[3,5],[6,7],[8,10],[12,16],
insert and merge [4,9] in
as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps
with [3,5],[6,7],[8,10].

注意O(n)一趟遍历的算法当然是很好想的，但打动不了面试官，既然都给你排序好了，当然要利用这点，用二分查找，这样算法是O(logN)的。

class Interval_cmp:public binary_function<Interval,int,bool>
{
public:
    virtual bool operator()(const Interval& ,const int&) =0;
};
class Interval_cmp_start:public Interval_cmp
{
public:
	bool operator()(const Interval& i1, const int& st)
	{
		return i1.start<st;
	}
};

class Interval_cmp_end:public Interval_cmp
{
public:
	bool operator()(const Interval& i1, const int& end)
	{
		return i1.end<end;
	}
};
class Solution {
public:
    vector<Interval> insert(vector<Interval> &inters, Interval newInterval) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
	    
	    vector<Interval> ret;
		Interval_cmp_start start_pred=Interval_cmp_start();
		Interval_cmp_end end_pred=Interval_cmp_end();

	    int start=newInterval.start;
	    int end=newInterval.end;
	    int idxStart= findInsertPos(inters,start,start_pred);
	    int idxEnd = findInsertPos(inters,end,end_pred);
	    
	    if ( idxStart>0 && start<=inters[idxStart-1].end)
	    {
		    start=inters[idxStart-1].start;
		    idxStart--;
	    }
	    if (idxEnd<inters.size() && end>=inters[idxEnd].start)
	    {
		    end=inters[idxEnd].end;
		    idxEnd++;
	    }
	
	    for(int i=0;i<idxStart;i++)
		    ret.push_back(inters[i]);
	    ret.push_back(Interval(start,end));
	    for(int i=idxEnd;i<inters.size();i++)
		    ret.push_back(inters[i]);
	    return ret;
    }
    int findInsertPos(vector<Interval>& inters,int k,Interval_cmp& pred)
    {
	    int l=0,r=inters.size()-1;
	    while(l<=r)
	    {
		    int mid=(l+r)>>1;
		    if ( pred(inters[mid],k) )
			    l=mid+1;
		    else
			    r=mid-1;
	    }
	    return l;
    }

};