Maximum Number of Non-Overlapping Intervals

You are given a list of time intervals in the format \(HH:MM-HH:MM\). Your task is to select as many non-overlapping intervals as possible. In other words, find the maximum number of intervals such that no two intervals overlap.

Note: Two intervals \(a\) and \(b\) are considered non-overlapping if the start time of \(b\) is not earlier than the end time of \(a\) (i.e. they can touch but not intersect).

Input Format: The first line of input contains an integer \(T\) indicating the number of intervals. This is followed by \(T\) lines, each containing a time interval in the format \(HH:MM-HH:MM\).

Output Format: Output a single integer representing the maximum number of non-overlapping intervals that can be selected.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

1. The first line contains an integer \(T\) representing the number of intervals.
2. The following \(T\) lines each contain a string representing a time interval in the format HH:MM-HH:MM.

outputFormat

Output a single integer to standard output (stdout), the maximum number of non-overlapping intervals that can be chosen.

3
09:00-11:00
10:30-12:00
12:00-13:00

2