Maximizing Non-Overlapping Updates

You are given a set of update requests. Each update request is represented as an interval with a start time and an end time. Your task is to determine the maximum number of non-overlapping update requests that can be selected. This is a typical interval scheduling problem.

The problem can be formulated as follows: Given a list of intervals \( (s_i, e_i) \) where \( s_i \) and \( e_i \) denote the start and end times respectively, select as many intervals as possible such that no two intervals overlap. An interval \( (s_i, e_i) \) is considered non-overlapping with another interval \( (s_j, e_j) \) if \( s_i \geq e_j \) or \( s_j \geq e_i \). A greedy strategy that sorts the intervals by their end times is optimal for this problem.

Input Example: For update requests [(1, 5), (3, 7), (6, 8), (2, 4)], selecting intervals \( (2,4) \) and \( (6,8) \) yields a maximum set of 2 non-overlapping updates.

inputFormat

The input is given via stdin and follows the format below:

• The first line contains a single integer \( n \) which denotes the number of update requests.
• The following \( n \) lines each contain two space-separated integers representing the start time and end time of an update request.

For example:

4
1 5
3 7
6 8
2 4

outputFormat

Output a single integer via stdout which is the maximum number of non-overlapping update requests.

For the input above, the correct output is:

2

## sample

1
1 2

1

</p>