📚 Table of Contents
📋 Problem Statement
Input: list of intervals [start,end]. Merge if overlapping.
Example:
[[1,3],[2,6],[8,10],[15,18]] -> [[1,6],[8,10],[15,18]]🎯 Real-World Analogy
Merging Calendar Blocks
Sort meetings by start time. Walk left-to-right; if current starts before previous ends, extend previous block.
💡 Key Insights
- Sort by interval start first.
- Maintain last merged interval in output.
- If overlap: update end to max(end1,end2).
- If no overlap: append new interval.
💻 Solution Approach
Time: O(N log N) | Space: O(N)
Python Implementation
from typing import List
def merge(intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0][:]]
for start, end in intervals[1:]:
last = merged[-1]
if start <= last[1]:
last[1] = max(last[1], end)
else:
merged.append([start, end])
return mergedJavaScript Implementation
function merge(intervals) {
if (intervals.length === 0) return [];
intervals.sort((a, b) => a[0] - b[0]);
const merged = [[intervals[0][0], intervals[0][1]]];
for (let i = 1; i < intervals.length; i++) {
const [start, end] = intervals[i];
const last = merged[merged.length - 1];
if (start <= last[1]) {
last[1] = Math.max(last[1], end);
} else {
merged.push([start, end]);
}
}
return merged;
}🔍 Step-by-Step Walkthrough
- Sorted: [1,3],[2,6],[8,10],[15,18]
- [2,6] overlaps [1,3] -> merge to [1,6]
- [8,10] no overlap -> append
- [15,18] no overlap -> append
⚡ Complexity Analysis
Time: O(N log N) dominated by sorting.
Space: O(N) for merged output.
🔧 Edge Cases
- Empty input
- Single interval
- Fully overlapping chain
- Already non-overlapping intervals
- Touching boundaries like [1,4] and [4,5]
🧪 Test Cases
[[1,3],[2,6],[8,10],[15,18]]->[[1,6],[8,10],[15,18]][[1,4],[4,5]]->[[1,5]][[1,4],[2,3]]->[[1,4]][]->[]
💼 Interview Tips
- Mention sorting prerequisite explicitly.
- Clarify overlap condition
current.start <= last.end. - Discuss in-place merge variant vs new output list.
🎓 Key Takeaways
- Sort + linear sweep is the standard interval-merging pattern.
- Only compare against last merged interval after sorting.