Maximum Number of Non-overlapping Activities

You are given a list of activities, each with a start time and an end time. Your task is to select the maximum number of activities that do not overlap with each other. An activity (i) is represented as a pair ((s_i, e_i)), where (s_i) is the start time and (e_i) is the end time. Two activities (i) and (j) are non-overlapping if (s_j \ge e_i) (assuming (e_i \le e_j) after sorting by end times).

The problem can be efficiently solved using a greedy algorithm where you first sort the activities by their end times and then iteratively select activities that start after or at the end time of the last selected activity.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer (n) representing the number of activities. Each of the next (n) lines contains two space-separated integers denoting the start time and end time of an activity.

outputFormat

Output a single integer representing the maximum number of non-overlapping activities that can be selected.## sample

5
1 2
3 4
0 6
5 7
8 9

4