Maximize Non-Overlapping Performances

Given a list of performance intervals, your task is to determine the maximum number of performances that can be scheduled without overlapping. Each performance is represented by a start time and an end time. Two performances do not overlap if the start time of the later performance is greater than or equal to the end time of the earlier one.

The problem can be formally described as follows: You are given a set of intervals ( I = {[s_i, f_i]} ). Find the largest subset of these intervals such that for any two consecutive intervals ( [s_i, f_i] ) and ( [s_j, f_j] ) in the chosen subset (with ( i < j )), the condition ( s_j \ge f_i ) holds.

A greedy strategy that sorts the intervals by finish times and then selects the intervals accordingly is an optimal solution.

inputFormat

The input is given via standard input (stdin). The first line contains an integer ( n ) representing the number of performances. Each of the following ( n ) lines contains two space-separated integers ( s ) and ( f ), which stand for the start time and the finish time of a performance, respectively.

outputFormat

Output a single integer to standard output (stdout) representing the maximum number of non-overlapping performances that can be scheduled.## sample

4
1 4
2 3
3 5
7 8

3