Given a set of intervals, return the minimum number you must remove so the rest do not overlap. e.g. [[1,2],[2,3],[3,4],[1,3]] → 1 (remove [1,3]).
Recognising the classic greedy 'activity selection' — sort by END time and keep the interval that finishes earliest whenever there's a conflict.
Minimising removals is the same as maximising how many intervals you keep without overlap — the classic interval-scheduling / activity-selection problem, and it is greedy, not DP. Sort by END time; walk through tracking the end of the last kept interval. If the next interval starts at or after that end, keep it and advance the end; otherwise it overlaps, so count a removal and skip it. Keeping the earliest-finishing interval at each conflict is provably optimal because it leaves the most room for the rest (an exchange argument). Removals = total − kept. The distinct signal versus merge-intervals is the objective: merge/insert wants to combine overlaps and sorts by START, while scheduling wants to select a maximum non-overlapping set and sorts by END. O(n log n) for the sort.
Maximise how many intervals fit without overlap (or minimise removals) → greedy: sort by END time and keep the earliest finisher on each conflict.
Time O(n log n) · Space O(1)