Q26: Merge Intervals
Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return an array of non-overlapping intervals that cover all intervals in the input.
Interval Sorting and Merging
function merge(intervals) {
if (!intervals.length) return [];
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const current = intervals[i];
const lastMerged = merged[merged.length - 1];
if (current[0] <= lastMerged[1]) {
lastMerged[1] = Math.max(lastMerged[1], current[1]);
} else {
merged.push(current);
}
}
return merged;
}
console.log(merge([[1,3],[2,6],[8,10],[15,18]])); // [[1,6],[8,10],[15,18]]💡 After sorting by start time, we iterate through intervals. If the current interval start is <= the previous interval end, we merge by expanding the previous end time; otherwise, we append the interval as a new non-overlapping range.
Key Takeaways
- Sort intervals by start time first to enable linear single-pass merging.
- Overlaps occur when the next interval's start time is less than or equal to the current interval's end time.
Knowledge Check
What is the time complexity of the Merge Intervals algorithm?