Merge Intervals
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.
Solution:
Sort all intervals based on the start first. Then, we could iterate through the interval list and compare current and last interval, if they are overlapped, extend the last interval; if they are not overlapped, save the last to result list and set current to last.
Code:
/**
* Definition of Interval:
* public class Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
*/
class Solution {
/**
* @param intervals, a collection of intervals
* @return: A new sorted interval list.
*/
public List<Interval> merge(List<Interval> intervals) {
if (intervals == null || intervals.size() <= 1) {
return intervals;
}
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
});
List<Interval> res = new ArrayList<>();
Interval last = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
Interval cur = intervals.get(i);
if (cur.start <= last.end) {
last.end = Math.max(last.end, cur.end);
} else {
res.add(last);
last = cur;
}
}
res.add(last);
return res;
}
}