Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Merge Intervals

LeetCode #56Medium
Sort by start · extend while overlapping

Given an array of intervals, merge all overlapping intervals and return the non-overlapping intervals that cover all the input.

Asked atAmazonGoogleMetaMicrosoft
step 1 / 6
[0,2]
[1,3]
[5,6]
[7,8]
0
1
2
3
4
5
6
7
8
[0][1][2][3][4][5][6][7][8]
Sort + one-pass sweep
▸
1sort intervals by start
2out ← []
3cur ← intervals[0]
4for b in intervals[1:]:
5    if b.start <= cur.end: cur.end = max(cur.end, b.end)
6    else: out.append(cur); cur ← b
7out.append(cur); return out
state
  • sorted[0,2] [1,3] [5,6] [7,8]

line 1Merge all overlapping intervals into the smallest set of disjoint intervals. Start by SORTING by start time — then any interval can only overlap the one immediately before it.