Skip to main content
Intervals

Merge Intervals

Sort intervals by start time. Walk through them: if the current interval overlaps with the previous one (start ≤ prev end), merge them by extending the end. Otherwise, start a new group.

O(n log n)
·
O(n)

How It Works

Merging intervals collapses a set of possibly overlapping ranges into a minimal set of disjoint ones. Sort by start time first — this guarantees that any interval that can merge with the current group appears immediately after it. Then sweep once: if the next interval starts at or before the current merged interval's end, extend the end to the maximum of the two; otherwise close the group and start a new one.

Without sorting, overlap detection requires comparing all O(n²) pairs and merging can cascade unpredictably. With it, one linear pass suffices, making the total O(n log n) dominated by the sort, with O(n) output space. The same skeleton underlies meeting-room, calendar, and range-coverage problems.

Step-by-Step Visualization

Merge overlapping intervals
1
0
3
1
2
2
6
3
8
4
10
5
15
6
18
7
Sorted[1,3], [2,6], [8,10], [15,18]
1/3

Code

Java
static int[][] merge(int[][] intervals) {
  Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
  List<int[]> result = new ArrayList<>();
  result.add(intervals[0]);

  for (int i = 1; i < intervals.length; i++) {
    int[] last = result.get(result.size() - 1);
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      result.add(intervals[i]);
    }
  }
  return result.toArray(new int[0][]);
}
// merge({{1,3},{2,6},{8,10},{15,18}}) → {{1,6},{8,10},{15,18}}

Tips & Gotchas

1Sort by start time
2If current interval overlaps with previous, merge by extending end
3Otherwise, add a new interval to result

Practice Problems

  • 1Merge Intervals
  • 2Meeting Rooms
  • 3Interval List Intersections
  • 4Employee Free Time

About the Intervals Pattern

Problems involving ranges [start, end] — meetings, schedules, overlapping segments. The key first step is almost always: sort by start time (or end time). Then process them linearly.

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

  • Two Sum
  • Best Time to Buy & Sell Stock
  • Maximum Subarray
  • Merge Intervals
  • Product of Array Except Self
  • Container With Most Water

Frequently Asked Questions

Why sort by start time rather than end time for merging?

Sorting by start ensures every interval overlapping the current group appears before any interval that is fully to its right, so a single forward sweep never needs to revisit closed groups. End-time sorting is the right tool for a different job — greedy activity selection.

Do touching intervals like [1,3] and [3,5] count as overlapping?

It depends on the problem's definition — some treat shared endpoints as mergeable, others as disjoint. Check whether the comparison should be next.start <= current.end or a strict inequality, and be consistent; this boundary is the most common source of wrong answers.