Maximum Non-Overlapping Intervals

You are given N intervals on a number line, each specified by a start and an end point. Your task is to select the maximum number of intervals such that none of them overlap. Two intervals \([a, b]\) and \([c, d]\) are considered non-overlapping if and only if \(c \geq b\) (i.e. the start of one is not less than the end of the other). A greedy strategy that sorts intervals by their end times will yield an optimal solution.

inputFormat

The first line of input contains an integer N representing the number of intervals. Each of the following N lines contains two space-separated integers representing the start and end points of an interval.

outputFormat

Print a single integer representing the maximum number of non-overlapping intervals that can be selected.

3
1 2
2 3
3 4

3