Last active
December 5, 2019 06:20
-
-
Save sr6033/58fd05ae4df0f2fb6fe8d2e726a92c46 to your computer and use it in GitHub Desktop.
Merge Overlapping Intervals
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| Given a collection of intervals, you have to merge all overlapping intervals. | |
| For example: Given [2,6],[5,10],[15,18], return [2,10],[15,18]. | |
| Also, mark that the returned intervals list should in non-decreasing order. | |
| -------------------------------------------------------------------------- | |
| struct Interval { | |
| int start; | |
| int end; | |
| }; | |
| */ | |
| bool compareInterval(Interval i1, Interval i2) | |
| { | |
| return (i1.start < i2.start); | |
| } | |
| vector<Interval> merge_interval(vector<Interval> &A) { | |
| sort(A.begin(), A.end(), compareInterval); | |
| vector<Interval> arr; | |
| arr.push_back(A[0]); | |
| int k = 0; | |
| for(int i = 1; i < A.size(); i++) | |
| { | |
| if(max(arr[k].start, arr[k].end) >= min(A[i].start, A[i].end)) | |
| { | |
| if(arr[k].end <= A[i].end) | |
| arr[k].end = A[i].end; | |
| } | |
| else | |
| { | |
| arr.push_back(A[i]); | |
| k++; | |
| } | |
| } | |
| return arr; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment