v9.1.1
Menu

Merge Intervals

mediumFREEIntervals & SchedulingUber DSA

Given a list of intervals [start, end], merge all overlapping intervals and return the result.

Two intervals overlap if they share at least one point, so intervals that only touch (e.g. [1, 4] and [4, 5]) are merged. The input is not guaranteed to be ordered.

Input: intervals, a list of [start, end] pairs (the example shows them as start:end, comma-separated). Output: a list of the merged [start, end] intervals, ordered by increasing start (the example prints one per line).

Example

Input
1:3,2:6,8:10,15:18
Output
1 6
8 10
15 18
Reasoning
  • The input is a list of four closed intervals on the number line: [1,3][1, 3], [2,6][2, 6], [8,10][8, 10] and [15,18][15, 18].
  • Two intervals [a,b][a, b] and [c,d][c, d] with a≤ca \le c overlap exactly when c≤bc \le b: the later one begins before (or at the moment) the earlier one finishes.
  • [1,3][1, 3] and [2,6][2, 6]: 2≤32 \le 3, so they overlap. Their union runs from min⁡(1,2)=1\min(1, 2) = 1 to max⁡(3,6)=6\max(3, 6) = 6, giving [1,6][1, 6].
  • [1,6][1, 6] and [8,10][8, 10]: 8>68 > 6, so there is a gap of 2 units and they stay separate. Likewise 15>1015 > 10 keeps [15,18][15, 18] on its own.
  • The result is 1 6, 8 10, 15 18: three disjoint intervals covering exactly the same points as the input, listed by increasing start.
  • Notice that touching ends count as overlapping ([1,4][1, 4] and [4,5][4, 5] become [1,5][1, 5]), and the input need not arrive in order: [1,4][1, 4] and [0,4][0, 4] become [0,4][0, 4].

Constraints

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2

More from Uber DSA

solution.py

Test results

Sign in to run your code against the test cases.