Javascript (ES6)
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
const merge = (intervals) => {
intervals.sort((a, b) => a[0] - b[0]);
const ret = [];
let prev = null;
for (const interval of intervals) {
if (prev != null) {
if (interval[0] > prev[1]) {
ret.push(prev);
prev = interval;
} else {
// Merge case.
prev[1] = Math.max(interval[1], prev[1]);
}
} else {
prev = interval;
}
}
if (prev !== null) {
ret.push(prev);
}
return ret;
};
console.log(merge([
[1, 3],
[2, 6],
[8, 10],
[15, 18]
])); // [[1,6],[8,10],[15,18]]
Demo
If “n” is the length of the input list, then the “Time Complexity” is O(nlogn).
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List < Interval > merge(List < Interval > intervals) {
// Sort the input list by the start times.
Collections.sort(intervals, (a, b) -> a.start - b.start);
List < Interval > ret = new ArrayList < Interval > ();
Interval prev = null;
for (Interval curr: intervals) {
if (prev == null) {
prev = curr;
} else {
if (curr.start <= prev.end) {
prev.end = Math.max(curr.end, prev.end);
} else {
ret.add(prev);
prev = curr;
}
}
}
if (prev != null) {
ret.add(prev);
}
return ret;
}
}