Fewest Talk Cancellations

medium

A festival booked one stage and way too many talks, each [start, end]. Talks that overlap can't share the stage, so some must be cancelled — and the organizer wants to cancel as few as possible.

Return the minimum number of talks to cancel so the remaining ones never overlap. A talk ending exactly when another starts is fine — applause, swap mics, go.

Example 1

in talks = [[1, 2], [2, 3], [3, 4], [1, 3]]

out 1

Cancel [1, 3]; the other three chain back-to-back.

Example 2

in talks = [[1, 2], [1, 2], [1, 2]]

out 2

Triplicate booking — only one copy can survive.

Constraints

· 1 <= len(talks) <= 2000
· -5 * 10^4 <= start < end <= 5 * 10^4