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 vector<Interval> merge(vector<Interval> &intervals)
02 {
03      vector<Interval> result;
04      int n=intervals.size();
05      if(n==0)
06          return result;
07      int min=intervals[0].start;
08      int max=intervals[0].start;
09      for(int i=0;i<n;i++){
10          int val=intervals[i].start;
11          if(min>val)
12              min=val;
13          if(max<val)
14              max=val;
15      }
16      int m=maxmin+1;
17      Interval* A=new Interval[m];
18      for(int i=0;i<m;i++){
19          A[i].start=i+min;
20          A[i].end=i+min1;
21      }
22      for(int i=0;i<n;i++){
23          int s=intervals[i].start;
24          int t=intervals[i].end;
25          int index=smin;
26          if(t>A[index].end){
27              A[index].end=t;
28          }
29      }
30      max=A[0].end;
31      min=A[0].start;
32      for(int i=0; ;i++){
33          int left=A[i].start;
34          int right=A[i].end;
35          if(left>right)
36              continue;
37          if(left<=max){
38              max=max>right?max:right;
39          }else{
40              Interval tmp(min, max);
41              result.push_back(tmp);
42              min=left;
43              max=right;
44          }
45          if(i==m1){
46              Interval tmp(min, max);
47              result.push_back(tmp);
48              return result;
49          }
50      }
51 }
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