Katkat
Back

Merge overlapping closed intervals into a sorted list of disjoint intervals

ByteDanceSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Coding problem: given closed integer intervals in any order, merge every group of overlapping or touching intervals and return the disjoint result sorted by start. It tests interval reasoning, correct handling of shared endpoints, duplicates and nested intervals, and a well-defined output order.

You are given a list of closed intervals with integer endpoints, in no particular order. Merge every group of intervals that overlap, and return the resulting intervals sorted by their start.

Function Signature

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:

intervals[i] = [start, end] is the closed interval from start to end, including both endpoints.

Rules

  • Two intervals overlap when they share at least one point. Intervals that only touch, such as [1, 4] and [4, 5], overlap because both contain 4. Intervals such as [1, 2] and [3, 4] share no point and do not overlap.
  • Merging is transitive: if A overlaps B and B overlaps C, all three become one interval, even when A and C do not overlap each other.
  • A merged interval is [smallest start, largest end] over its group.
  • The input may contain duplicate intervals and intervals contained in other intervals.
  • Return the merged intervals sorted by start in ascending order. Merged intervals are pairwise disjoint, so this order is unique.

Constraints

  • 1 <= len(intervals) <= 10^4
  • 0 <= start <= end <= 10^9 for every interval

Examples

Example 1

Input: intervals = [[2, 5], [9, 12], [4, 7], [13, 15]]
Output: [[2, 7], [9, 12], [13, 15]]

[2, 5] and [4, 7] share the points 4 and 5, so they merge into [2, 7]. [9, 12] and [13, 15] share no point, so they stay separate.

Example 2

Input: intervals = [[6, 8], [1, 6]]
Output: [[1, 8]]

The two intervals touch at 6, which counts as overlapping. The output is sorted by start even though the input was not.

Example 3

Input: intervals = [[5, 7], [1, 2], [3, 4], [2, 3], [9, 9]]
Output: [[1, 4], [5, 7], [9, 9]]

[1, 2], [2, 3] and [3, 4] chain together through the shared points 2 and 3. [1, 4] and [5, 7] share no point, so they stay separate, and [9, 9] is a single point.