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

Thoughts:
We first sort the list according to the start-time. Then for any interval $i$ in the middle, it has overlap with the next interval $j$ iff $j$.start <= $i$.end. If so, we know we are about to merge them into a new interval $k$. And $k$.start = $i$.start && $k$.end = $\max(i$.end, $j$.end).

Code (Java):

public class Solution {
public class MyComparator implements Comparator{
public int compare(Object o1, Object o2) {
Interval i1 = (Interval)o1;
Interval i2 = (Interval)o2;
return i1.start - i2.start;
}
}

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
if(intervals == null)
return null;
ArrayList<Interval> result = new ArrayList<Interval>();
if(intervals.size() == 0)
return result;
if(intervals.size() == 1) {
return result;
}
Collections.sort(intervals, new MyComparator());
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for(int i = 1; i < intervals.size(); ++i) {
Interval curr = intervals.get(i);
if(curr.start <= end) {
end = Math.max(end, curr.end);
} else {
start = curr.start;
end = curr.end;
}
}
return result;
}
}

Code (C++):
Thanks to this post:

class Solution {
class Solution {
public:
struct MyComparatorClass {
bool operator() (Interval i, Interval j) { return (i.start < j.start);}
} myComparator;

vector<Interval> merge(vector<Interval> &intervals) {
vector<Interval> result;
if(intervals.size() == 0)
return result;
if(intervals.size() == 1) {
result.push_back(intervals[0]);
return result;
}
sort(intervals.begin(), intervals.end(), myComparator);
vector<Interval>::iterator it = intervals.begin();
Interval current = *(it)++;
while (it != intervals.end()){
if (current.end >= it -> start) {
current.end = std::max(current.end, it -> end);
} else {
result.push_back(current);
current = *(it);
}
it++;
}
result.push_back(current);
return result;
}
};