Maximum Non-Overlapping Events

You are given a list of events, each with a start time and an end time. Each event is represented by two integers in 24-hour format; for example, an event could be represented as 0900 for starting at 9:00 AM and 1100 for ending at 11:00 AM.

Your task is to determine the maximum number of events one can attend without any overlap. Two events are considered overlapping if one event starts before the previous one has finished. A well-known greedy strategy to solve this problem is to always pick the event that ends earliest, thereby leaving as much room as possible for subsequent events.

Mathematical formulation:

Let \(E = \{(s_i, e_i)\}\) denote the set of events, where \(s_i\) and \(e_i\) are the start and end times respectively. We want to compute the maximum size of a subset \(S \subseteq E\) such that for any two events \((s_i, e_i)\) and \((s_j, e_j)\) in \(S\) with \(i \neq j\), either \(e_i \leq s_j\) or \(e_j \leq s_i\).

inputFormat

The input is given via standard input (stdin). The first line contains an integer (n) representing the number of events. Each of the next (n) lines contains two integers denoting the start time and the end time of an event.

outputFormat

Output a single integer to standard output (stdout) that represents the maximum number of non-overlapping events that can be attended.## sample

3
0900 1100
1000 1230
1200 1300

2