Maximum Number of Non-Overlapping Activities

You are given a set of activities, each specified by a start time and an end time. Two activities are considered non-overlapping if the start time of one is not less than the end time of the other. More formally, an activity with start time \(s\) and end time \(e\) does not overlap with an activity that ended at time \(t\) if \(s \ge t\). Your task is to select as many non-overlapping activities as possible.

The problem is a classic greedy algorithm problem known as the Activity Selection Problem. The optimal solution can typically be obtained by sorting the activities by their end times and then selecting each activity that starts after or exactly when the previous one ended.

Note: The scheduling condition can be expressed in LaTeX as \(s_i \geq e_j\), where \(s_i\) is the start time of the current activity and \(e_j\) is the finish time of the last selected activity.

inputFormat

The input is given via standard input (stdin) and has the following format:

n
s1 e1
s2 e2
... 
sn en

Where:

• n is an integer representing the number of activities.
• Each of the next n lines contains two integers si and ei representing the start and end times for the \(i^{th}\) activity.

You may assume that all times are non-negative integers.

outputFormat

The output should be a single integer written to standard output (stdout) which represents the maximum number of non-overlapping activities that can be scheduled.

## sample

1
1 2

1