You are handed a list of job requests, each a half-open interval [start, end) of time it needs a shared machine. The machine runs one job at a time, so you must drop some requests until no two remaining jobs overlap. Two jobs that only touch at an endpoint ([a, b) and [b, c)) do not conflict and may both stay.
Output the minimum number of jobs you must remove to make the surviving set pairwise non-overlapping. This count is uniquely determined even though the specific set removed may not be.
Input format
Line 1: an integer n — the number of jobs.
Next n lines: two integers start end describing one job [start, end).
Output format
A single integer: the minimum number of jobs to remove.
Constraints
- 1 <= n <= 100000
- -1000000000 <= start < end <= 1000000000
- Jobs are given in arbitrary order and may overlap in any pattern.