Intervals · LC #56
Merge Intervals
Sort intervals by start time, then greedily merge overlapping ones by extending the end of the last kept interval. Returns the minimal non-overlapping cover.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an array of intervals `[start, end]`, merge all overlapping intervals and return the resulting array.
Sample I/O
Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Input: [[1,4],[4,5]] Output: [[1,5]]
Intuition
How to Think About It
Intuition
After sorting by start, any overlapping interval must have a start ≤ the current open interval's end. Extending the end greedily is always safe because no future interval can "bridge" a gap that doesn't exist.
Core Concept
Sort by start → single-pass linear scan keeping a mutable "last interval". Overlap condition: next.start ≤ last.end. Merge by updating last.end = max(last.end, next.end).
When to use
Any problem asking for a non-overlapping cover, free-time windows, or merging ranges (e.g., calendar events, IP ranges, log spans).
When NOT to use
When you need to track which original intervals participated in each merge, or when intervals arrive in a streaming fashion (use an interval tree instead).
Key Insights
What to Know Cold
- Sorting by start guarantees all potentially-overlapping intervals are adjacent.
- Overlap check is: intervals[i][0] <= result.back()[1].
- Merge by taking max of both ends - not just the new interval's end.
- Edge case: [[1,4],[4,5]] - touching intervals (start == end) must also merge.
- Result array doubles as the "working set"; no extra data structure needed.
1 example
Worked Examples
Merge overlapping calendar blocks
Busy slots [[1,3],[2,6],[8,10],[15,18]] - compute free windows.
Sort by start, iterate and extend last interval on overlap.
Output: [[1,6],[8,10],[15,18]]
Calendar / scheduling systems reduce overlapping bookings to canonical non-overlapping blocks before further processing.