Maximum Non-overlapping Workshops

You are given a schedule of N workshops, where each workshop is defined by its start time S_i and end time E_i. Your task is to compute the maximum number of workshops an employee can attend without any overlap.

Two workshops are considered non-overlapping if the start time of the current workshop is greater than or equal to the finish time of the previously selected workshop. Formally, given a set of workshops \(\{(S_1, E_1), (S_2, E_2), \dots, (S_N, E_N)\}\), you need to select the largest possible subset such that \(E_{i} \leq S_{j}\) for any two consecutively chosen workshops \(i\) and \(j\).

This problem can be optimally solved by a greedy algorithm: sort the workshops by their finish times in ascending order, and then select workshops by iterating through the sorted list and picking those that start after or exactly when the last selected workshop finished.

inputFormat

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

• The first line contains an integer N representing the number of workshops.
• The next N lines each contain two integers separated by a space, denoting the start time S_i and end time E_i of each workshop.

outputFormat

Output a single integer which represents the maximum number of non-overlapping workshops that can be attended. The result should be printed to standard output (stdout).## sample

3
1 3
2 5
4 6

2