IntervalsGreedySorting
Find the minimum number of intervals you must remove so that the remaining intervals do not overlap. Intervals that only touch at an endpoint, like [1, 2] and [2, 3], do not overlap.
Input
Line 1: n. Next n lines: the start and end of each interval.
Output
Print the minimum number of intervals to remove.
Constraints
1 <= n <= 1500 -10^4 <= start < end <= 10^4
Example 1
Input
4 1 2 2 3 3 4 1 3
Output
1
Removing [1,3] leaves three non-overlapping intervals.
Example 2
Input
3 1 2 1 2 1 2
Output
2
Two of the three identical intervals must go.