Merge Overlapping Intervals Solution InterviewBit

 

Merge Overlapping 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].

Make sure the returned intervals are sorted.

/**

 * Definition for an interval.

 * struct Interval {

 *     int start;

 *     int end;

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

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

 * };

 */

 bool cmp(Interval &a,Interval &b){

     if(a.start==b.start)return a.end<b.end;

     return a.start<b.start;

 }

 

vector<Interval> Solution::merge(vector<Interval> &v) {

   

    vector<Interval>ans;

    sort(v.begin(),v.end(),cmp);

    Interval s=v[0];

    for(int i=1; i<v.size(); i++){

        if(v[i].start>s.end){

            ans.push_back(s);

            s=v[i];

        }

        else if(v[i].start<=s.end){

            s.end=max(s.end,v[i].end);

        }

    }

    ans.push_back(s);

    return ans;

   

}