Monday, November 25, 2013

LeetCode Problem : Merge Intervals

Problem 


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

Code

class Comp
{
public:
    bool operator()(const Interval &i1,const Interval &i2){
        return (i1.start < i2.start);
    }
};
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<Interval> result;
        sort(intervals.begin(),intervals.end(),Comp());
        int n = intervals.size();
        int i = 0;
        while(i < n){
            int j = i;
            int finish = intervals[j].end;
            while(j < n - 1 && finish >= intervals[j + 1].start){
                ++j;
                finish = max(finish,intervals[j].end);
            }
            result.push_back(Interval(intervals[i].start,finish));
            i = j + 1;
        }
        return result;
    }
};

No comments:

Post a Comment