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]]
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; } }