# Merge Intervals

## Question

### Problem Statement

Given a collection of intervals, merge all overlapping intervals.

#### Example

Given intervals => merged intervals:

[                     [
[1, 3],               [1, 6],
[2, 6],      =>       [8, 10],
[8, 10],              [15, 18]
[15, 18]            ]
]


#### Challenge

O(n log n) time and O(1) extra space.

## 题解1 - 排序后

### Java

/**
* Definition of Interval:
* public class Interval {
*     int start, end;
*     Interval(int start, int end) {
*         this.start = start;
*         this.end = end;
*     }
*/

class Solution {
/**
* @param intervals: Sorted interval list.
* @return: A new sorted interval list.
*/
public List<Interval> merge(List<Interval> intervals) {
if (intervals == null || intervals.isEmpty()) return intervals;

List<Interval> result = new ArrayList<Interval>();
// sort with Comparator
Collections.sort(intervals, new IntervalComparator());
Interval prev = intervals.get(0);
for (Interval interval : intervals) {
if (prev.end < interval.start) {
prev = interval;
} else {
prev.start = Math.min(prev.start, interval.start);
prev.end = Math.max(prev.end, interval.end);
}
}

return result;
}

private class IntervalComparator implements Comparator<Interval> {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
}

}


## 题解2 - 插入排序

### Java

/**
* Definition of Interval:
* public class Interval {
*     int start, end;
*     Interval(int start, int end) {
*         this.start = start;
*         this.end = end;
*     }
*/

class Solution {
/**
* @param intervals: Sorted interval list.
* @return: A new sorted interval list.
*/
public List<Interval> merge(List<Interval> intervals) {
if (intervals == null || intervals.isEmpty()) return intervals;

List<Interval> result = new ArrayList<Interval>();
for (Interval interval : intervals) {
result = insert(result, interval);
}

return result;
}

private List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> result = new ArrayList<Interval>();
int insertPos = 0;
for (Interval interval : intervals) {
if (newInterval.end < interval.start) {
} else if (newInterval.start > interval.end) {
insertPos++;
} else {
newInterval.start = Math.min(newInterval.start, interval.start);
newInterval.end = Math.max(newInterval.end, interval.end);
}
}

return result;
}
}