Remove the fewest intervals so the rest don't overlap. Sort by end time and keep whatever finishes first; every clash after that gets cut.
▼The problem
LeetCode 435 (Medium). Given a list of intervals, return the minimum number of intervals to remove so the rest don't overlap. Intervals that only touch at an endpoint, like [1,2] and [2,3], don't overlap.
Example: [[1,2],[2,3],[3,4],[1,3]] → 1 (remove [1,3]; the other three run back to back).
The solution
def erase_overlap_intervals(intervals):
intervals.sort(key=lambda iv: iv[1]) # by end
removed, end = 0, float('-inf')
for s, e in intervals:
if s >= end: # fits: keep it
end = e
else: # overlaps
removed += 1
return removedTranscript
Non-overlapping Intervals. Remove as few intervals as possible so the rest don't overlap. Touching ends, like one to two and two to three, are fine.
Picture one stage and four shows: one to two, two to three, three to four, and one to three. One to three clashes with two shows. Cancel it, and the rest run back to back. The answer is one.
You could try every subset of shows and keep the biggest with no clashes. But there are two to the n subsets. Far too slow.
Be greedy. Sort the shows by when they end, and always book the one that finishes first. It frees the stage soonest. Swap the first show of any best schedule for the earliest finisher: it ends no later, so everything after still fits.
Sorting by start is a trap. A long show, one to ten, starts first and blocks two short ones. Like Merge Intervals, it's a sort and one sweep, but the key is the end.
In code, remember the last kept end. If a show starts at or after it, keep the show and move the end. Otherwise, count it as removed.
Let's run it. Sorted by end: one to two, two to three, one to three, three to four. Keep one to two; the stage is free at two. Two to three fits; free at three. One to three starts too early: remove it. Three to four fits. One removed.
Sorting takes n log n time, and the sweep is one pass. Beyond the sort, just two variables: constant extra space.
Sort by end, keep what fits, count the rest. That's Non-overlapping Intervals.