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

Non-overlapping Intervals

LeetCode #435Medium
Sort by end · greedily keep early finishers

Given an array of intervals, return the minimum number of intervals you must remove so that the remaining intervals are non-overlapping.

Asked atAmazonGoogleBloomberg
step 1 / 7
[1,2]
[2,3]
[1,3]
[3,4]
0
1
2
3
4
[0][1][2][3][4]
Greedy by end time
▸
1sort intervals by end
2prevEnd ← −∞; removed ← 0
3for iv in intervals:
4    if iv.start >= prevEnd: keep; prevEnd ← iv.end
5    else: removed += 1   # iv ends later — drop it
6return removed
state
  • sorted by end[1,2] [2,3] [1,3] [3,4]

line 1Find the MINIMUM number of intervals to REMOVE so the rest are non-overlapping. The trick: SORT BY END TIME. [1,2] [2,3] [1,3] [3,4]. An interval that ends earliest leaves the most room for the others — so we greedily keep early finishers.