Non-overlapping Intervals
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Return the minimum number of intervals to remove so the rest do not overlap.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Is it better to keep the interval that starts first, or the one that ends first?
- Hint 2Sort by end. Track the end of the last kept interval.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
One hall, many event requests. To fit the most events, sort requests by when they end. Take the one finishing earliest. Then take the next one that starts after it finishes, and so on. Anything that clashes with a chosen event is sent away. The count of those sent away is the answer.
- The obvious way
Try every subset of intervals: O(2^n).
- The key insight
Sort by end time. Keep the first. For each next interval: if it starts at or after the kept end, keep it and update the end; otherwise it clashes, so count a removal. Finishing earliest never hurts what comes later.
- The algorithm
- Sort intervals by end.
- Keep the first; remember its end.
- Next interval starts >= remembered end? Keep it, remember its end.
- Otherwise count one removal.
Watch it run
Example[[1,2],[2,3],[3,4],[1,3]] (sorted by end: [1,2] [2,3] [1,3] [3,4])
Keep 1-2 (earliest to end). Kept end: 2.
removed 0
Where people slip
- Sort by END, not start; sorting by start gives wrong answers on a long early interval.
- Intervals that only touch (end = next start) do not clash.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def erase_overlap_intervals(intervals):
intervals.sort(key=lambda interval: interval[1]) # by end time
removed = 0
kept_end = float("-inf")
for start, end in intervals:
if start >= kept_end:
kept_end = end # no clash: keep it
else:
removed += 1 # clashes with a kept one: send it away
return removedNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.