AlgoInsight

DSA problem

Merge Intervals

MediumIntervalsPattern: Intervalstop75FreeAmazonGoogleMicrosoftFacebookBloomberg

Given an array of intervals intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all of the intervals in the input.

Two intervals overlap when one starts at or before the other ends. After merging, the resulting list must contain no overlaps and must collectively cover every point that was inside any original interval. The order of the output intervals is sorted by start time.

The crucial observation is that overlapping intervals form connected components on the number line, and once you sort by start time these components appear as contiguous runs of the sorted list. That means a single pass after sorting is enough — no pairwise comparison, no graph, no extra data structure.

The optimal approach sorts by start, then walks through the sorted list maintaining a "current" merged interval. For each new interval, if its start is less than or equal to the current end, extend the current end to the max of the two; otherwise close the current interval (append it to the result) and start a new current. Sorting dominates at O(n log n) time; the sweep is O(n) and uses O(1) auxiliary space beyond the output.

Examples

Example 1
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Sorted by start the list is already in order. [1,3] and [2,6] overlap (2 <= 3), so they merge into [1,6]. [8,10] and [15,18] do not overlap with anything.
Example 2
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Touching at a boundary counts as an overlap: 4 <= 4, so [1,4] and [4,5] merge into [1,5].
Example 3
Input: intervals = [[1,4],[2,3]]
Output: [[1,4]]
Explanation: [2,3] is fully contained inside [1,4]; the merged interval is just [1,4] because the end stays at max(4,3)=4.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

arrayintervalssorting

Browse all DSA problems