Non-overlapping Intervals

Given a list of intervals, find the minimum number you'd need to remove so that none of the remaining ones overlap.

Example

Input: [1,2] [2,3] [3,4] [1,3] Output: 1 (remove [1,3])

Approach

This is a classic "activity selection" greedy problem: sort by end time (not start), and greedily keep any interval whose start is at or after the end of the last interval you kept. Every interval that doesn't fit that rule has to be removed — sorting by end time is what makes the greedy choice provably optimal (it always keeps the option that frees up the earliest room for future intervals).

Input format

Line 1: number of intervals R Next R lines: start end

Print the minimum number of removals.