Activity Selection Problem

You are given a set of activities, each with a start time and a finish time. The goal is to determine the maximum number of activities that can be performed by a single person, assuming that only one activity can be performed at a time.

The problem can be described using the following parameters:

• n: The number of activities.
• activities: A list of activities where each activity is represented as a pair \( (s, f) \) denoting the start time \( s \) and the finish time \( f \).

Your task is to select the maximum number of non-overlapping activities. The well-known greedy algorithm helps in solving this problem efficiently by sorting the activities based on their finish times.

Formally, if the sorted activities are \( a_1, a_2, \ldots, a_n \) with finish times \( f_1 \le f_2 \le \ldots \le f_n \), then you need to find the largest subset \( \{a_{i_1}, a_{i_2}, \ldots, a_{i_k}\} \) such that \( f_{i_j} \le s_{i_{j+1}} \) for all valid \( j \).

inputFormat

The input is read from stdin and has the following format:

n
s1 f1
s2 f2
... 
 sn fn

Where:

• n is an integer representing the number of activities.
• Each of the next n lines contains two integers separated by space, representing the start time and finish time of an activity.

outputFormat

Output the maximum number of non-overlapping activities as an integer to stdout.

## sample

6
1 2
3 4
0 6
5 7
8 9
5 9

4

</p>