# LeetCode: Merge Intervals

By | 2012 年 10 月 5 日

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

## Analyze

This is a simple question, just sort the intervals by `start` first then check them one by one and merge adjacent intervals if necessary.

## Notes

• vector::back()，返回的是最后一个元素的引用
• sort(vec.begin(),vec.end(),customLessThan),customLessThan的原型
• vector::push_back(anItem)，会调用anItem的拷贝构造函数，将拷贝所得新的元素放入vector
• class的static数据成员，只能在类定义中声明；初始化需要在类定义之外用type className::aMember = initiaValue来进行

## Solutions:

### Ruby

```# Definition for an interval.
# class Interval
#     attr_accessor :start, :end
#     def initialize(s=0, e=0)
#         @start = s
#         @end = e
#     end
# end

def clone(interval)
Interval.new(interval.start, interval.end)
end

# @param {Interval[]} intervals
# @return {Interval[]}
def merge(intervals)
intervals.sort!{|inv1, inv2| inv1.start <=> inv2.start}
result = []
return result if intervals.empty?

opening = clone(intervals.first)
intervals[1..-1].each do |inv|
if opening.end >= inv.start
opening.end = inv.end if opening.end < inv.end
else
result << opening
opening = clone(inv)
end
end
result << opening

result
end
```

### C++, 4ms过小集合，但是不知道为什么大集合运行时错误

```/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
bool isEarlierThan(const Interval &int1, const Interval &int2){
return int1.start <= int2.start;
}
class Solution {
public:
vector<Interval> merge(vector<Interval> &intervals) {
sort(intervals.begin(),intervals.end(),isEarlierThan);
Interval *openInt = NULL;
vector<Interval> result;
for(int i = 0 ; i < intervals.size(); ++i) {
Interval &curInt = intervals[i];
if(openInt == NULL || openInt->end < curInt.start){
result.push_back(curInt);
openInt = &(result.back());
}else if(curInt.end > openInt->end) {
openInt->end = curInt.end;
}
}
return result;
}
};
```

### C++, Code rewrite at 2012-12-24, 60ms pass large set

```/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
static bool earlier(const Interval &int0, const Interval &int1) {
return int0.start < int1.start;
}
public:
vector<Interval> merge(vector<Interval> &intervals) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(intervals.size() <= 1) return intervals;
sort(intervals.begin(),intervals.end(),Solution::earlier);
vector<Interval> ret;
Interval openInt = intervals[0];
for(int i = 0; i < intervals.size(); ++i) {
Interval &cur = intervals[i];
if(openInt.end < cur.start) {
ret.push_back(openInt);
openInt = cur;
} else {
if (openInt.end < cur.end) openInt.end = cur.end;
}
}
ret.push_back(openInt);
return ret;
}
};
```