Activity Selection Problem

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 non-overlapping activities. An activity is denoted by the interval \( (s_i, f_i) \) where \( s_i \) is the start time and \( f_i \) is the finish time. Two activities \( (s_i, f_i) \) and \( (s_j, f_j) \) can be scheduled together if \( s_j \ge f_i \). The input is provided via standard input (stdin) and the result should be printed to standard output (stdout).

inputFormat

The first line of the input contains an integer \( n \) representing the number of activities. The next \( n \) lines contain two space-separated integers \( s_i \) and \( f_i \) for each activity, where \( s_i \) is the start time and \( f_i \) is the finish time.

outputFormat

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

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

4