How do you approach Merge Intervals?

The intervals arrive in arbitrary order. What ordering would put every overlap next to its neighbor?

What is the time complexity of Merge Intervals?

Time complexity: O(n log n) for the sort, O(n) sweep. Space complexity: O(n) for the output (O(log n) sort stack aside).

What are common mistakes on Merge Intervals?

Not sorting first. Nearly every interval algorithm assumes the list is ordered by start, and skipping that step gives answers that are right on the sample and wrong everywhere else. Treating touching intervals as overlapping (or not) without checking which the problem means. Mutating the input intervals while iterating over them.

gitGood.dev

← Back to problems

Merge Intervals

MediumAlgorithms

Description

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

Return the merged intervals sorted by start value in ascending order. Intervals that merely touch (one ends exactly where the next begins) are considered overlapping and should be merged.

Example 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Explanation: [1,3] and [2,6] overlap, so they merge into [1,6].

Example 2

Input: intervals = [[1,4],[4,5]]

Output: [[1,5]]

Explanation: [1,4] and [4,5] touch at 4, which counts as overlapping.

Example 3

Input: intervals = [[1,4],[2,3]]

Output: [[1,4]]

Explanation: [2,3] is entirely inside [1,4].

Constraints

- 1 <= intervals.length <= 10^4 - intervals[i].length == 2 - 0 <= start_i <= end_i <= 10^4

Merge Intervals: approach, complexity and pitfalls

A medium intervals problem, graded against 7 test cases (4 of them hidden).

The pattern: Intervals

Sorting by start or end, then merging or scheduling overlapping ranges.

Reach for it when you see: Meetings, bookings, ranges, or anything with a start and an end.

If you are stuck

Show the 3-step hint ladder

The intervals arrive in arbitrary order. What ordering would put every overlap next to its neighbor?
Sort by start. Then an interval either overlaps the last merged interval or starts a fresh one.
Overlap test after sorting: current.start <= lastMerged.end. On overlap, extend lastMerged.end to max(lastMerged.end, current.end).

The optimal approach

Show the approach: Sort, Then Sweep

Sort by start value. Sweeping left to right, each interval either overlaps the most recently merged interval (`start <= mergedEnd`, so extend the end with `max`) or begins a new disjoint block. Sorting guarantees no later interval can overlap an already-closed block.

Time: O(n log n) for the sort, O(n) sweep
Space: O(n) for the output (O(log n) sort stack aside)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Intervals mistakes

These apply to the pattern as a whole, not just this problem.

Not sorting first. Nearly every interval algorithm assumes the list is ordered by start, and skipping that step gives answers that are right on the sample and wrong everywhere else.
Treating touching intervals as overlapping (or not) without checking which the problem means.
Mutating the input intervals while iterating over them.