Given a list of intervals, remove the fewest intervals so that the rest do not overlap. Intervals that only touch at an end point do not overlap.
DSA Animator › DSA Revision › Intervals › Non-Overlapping Intervals
Remember: sort by end, and keep the one that finishes first. Removals equal n minus the most intervals you can keep. The video solves Non-Overlapping Intervals (LeetCode 435, Medium) with the Greedy by End pattern from the Intervals topic, and you can replay every step in the interactive Non-Overlapping Intervals animation.
Given a list of intervals, remove the fewest intervals so that the rest do not overlap. Intervals that only touch at an end point do not overlap.
For 1 to 2, 2 to 3, 3 to 4 and 1 to 3, remove just 1 to 3, so the answer is 1.
Trying every subset of intervals is exponential. Greedy works: always keep the interval that ends earliest.
Sort the intervals by end. Keep an interval if it starts at or after the end of the last kept one. Otherwise it overlaps, so remove it, and the earlier end leaves more room for the rest.
Sorted by end: 1 to 2, 2 to 3, 1 to 3, 3 to 4. Keep 1 to 2, then keep 2 to 3, because it starts at 2. 1 to 3 starts before 3, so remove it. 3 to 4 starts at 3, so keep it. One interval was removed.
In code, sort by the end value. Track the end of the last kept interval. If the next start is at least that end, keep it and update the end, otherwise count a removal. It's O of n log n time.
Remember: sort by end, and keep the one that finishes first. Removals equal n minus the most intervals you can keep.