Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-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. To minimize removed intervals (or maximize kept ones), we should prioritize intervals that finish early. This leaves the maximum room for subsequent intervals.

1. Sort by End Time: Sort intervals by end time ascending.
2. Iterate: Keep track of the prevEnd time (end time of the last kept interval).
3. Check: For each interval curr:
   • If curr.start >= prevEnd: No overlap using greedy choice. Keep it and update prevEnd = curr.end.
   • Else: Overlap detected. Since curr ends later (or same time) as our sorted prev, we prefer the prev one (already chosen) and remove curr.
   • Wait, actually since we sorted by end, if curr overlaps prev, curr MUST have a later or equal end time. So keeping prev is always optimal or neutral. Thus we blindly discard curr.