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

C++:
01 /**
02  * Definition for an interval.
03  * struct Interval {
04  *     int start;
05  *     int end;
06  *     Interval() : start(0), end(0) {}
07  *     Interval(int s, int e) : start(s), end(e) {}
08  * };
09  */
10 bool compare(Interval a, Interval b)
11 {
12     return a.start<b.start;
13 }
14 class Solution {
15 public:
16     vector<Interval> merge(vector<Interval> &intervals) {
17         // Start typing your C/C++ solution below
18         // DO NOT write int main() function
19         int i=0;
20         vector<Interval> result;
21         sort(intervals.begin(),intervals.end(),compare);
22         while(i<intervals.size())
23         {
24             int mergeStart=intervals[i].start;
25             int mergeEnd=intervals[i].end;
26             i++;
27             while(i<intervals.size()&&
28                   (intervals[i].start<=mergeEnd))
29             {
30                 mergeEnd=mergeEnd>intervals[i].end?
31                   mergeEnd:intervals[i].end;
32                 i++;
33             }
34             Interval A;
35             A.start=mergeStart;
36             A.end=mergeEnd;
37             result.push_back(A);
38         }
39         return result;
40     }
41 };
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s