Non-overlapping Intervals

Each entry of intervals is a pair [start, end]. Return the fewest intervals you have to delete so that none of the remaining ones overlap. Intervals that only touch at an endpoint, like [1,2] and [2,3], do not count as overlapping.

Example 1:

• Input: [[1,2],[2,3],[3,4],[1,3]]
• Output: 1
• Explanation: Remove [1,3] to handle the overlaps with [1,2] and [2,3].

This is a classic Greedy problem. Removing as few intervals as possible is the same as keeping as many as possible, and the interval that finishes earliest leaves the most room for everything after it.

1. Sort by End Time: Sort intervals by end ascending.
2. Keep the first: It ends earliest, so keep it and set prevEnd to its end.
3. Check each later interval curr:
   • If curr.start >= prevEnd, it does not overlap the last kept interval: keep it and set prevEnd = curr.end.
   • Otherwise it overlaps. Because of the sort, curr ends no earlier than the interval already kept, so keeping that one never leaves less room: remove curr and add 1 to the count.
4. Return the count.

See how sorting by End Time allows us to reliably pick the 'best' intervals to keep.