Description
Remove as few intervals as possible so the remaining intervals do not overlap. Touching endpoints are allowed.
Solution
def erase_overlap_intervals(intervals):
end = float('-inf')
removed = 0
for start,finish in sorted(intervals,key=lambda p:p[1]):
if start < end:
removed += 1
else:
end = finish
return removedExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[[1,3],[2,4],[3,5]]]- Output
1
Remove the middle interval to keep the touching outer pair.
Example 2
- Input
[[[1,2],[2,3]]]- Output
0
Touching endpoints do not overlap here.
Example 3
- Input
[[[1,2],[1,2],[1,2]]]- Output
2
Only one copy can remain.
Approach
Sort by end and greedily keep every interval that begins at or after the previous kept end.
Time & space
O(n log n) time; O(n) sorting space. Here n is the input length.