# [leetcode] Merge Intervals

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

10/7/2015 update

Runtime error, quite strange.

I don’t figure out why yet.

```/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
struct {
bool operator()(const pair<int, bool> a, const pair<int, bool> b){
if(a.first < b.first){
return true;
}
else if(a.first > b.first){
return false;
}
else{
if(a.second == true){
return true;
}
else{
return false;
}
}
}

} cmp;
class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals) {
vector<Interval> ans;
vector<pair<int, bool> > points; //x, true means start point, false means end point
for(auto interval : intervals){
points.push_back(make_pair(interval.start, true));
points.push_back(make_pair(interval.end, false));
}
sort(points.begin(), points.end(), cmp);
int count = 0;
int start = -1;
for(auto it = points.begin(); it != points.end(); it++){
auto point = *it;
if(point.second == true){
//left point
if(start == -1){
start = point.first;
}
count++;
}
else{
//right point
count--;
if(count == 0){
//end of a line segment
if(point.first > start){
ans.push_back(Interval(start, point.first));

}
start = -1;
}
}
}
return ans;
}
};```

```/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
struct{
bool operator()(Interval a, Interval b){
return a.start < b.start;
}
}cmp;
class Solution {
public:
vector<Interval> merge(vector<Interval> &intervals) {
vector<Interval> re;
if(intervals.empty()) return re;
sort(intervals.begin(),intervals.end(), cmp);
int start = intervals[0].start;
int end = intervals[0].end;
for(vector<Interval>::iterator it = intervals.begin(); it != intervals.end(); it++){
//overlap, extend 'end'
if((*it).start <= end){
end = (*it).end > end? (*it).end: end;
}
//not overlap
else{
Interval tmp = Interval(start, end);
re.push_back(tmp);
start = (*it).start;
end = (*it).end;
}
}
Interval tmp = Interval(start, end);
re.push_back(tmp);
return re;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.