Longest Sequence of Non-Overlapping Events

Given a list of events, each defined by a start and an end time in 24-hour (HH:MM) format, your task is to select a longest possible sequence of non-overlapping events. Two events are considered non-overlapping if the start time of an event is not earlier than the end time of the previous event in the sequence. This problem can be solved using a greedy algorithm that sorts the events by their ending times.

For example, consider the events:

• 09:00 11:00
• 11:00 13:00
• 10:00 11:30
• 13:00 15:00
• 12:00 13:30

The longest sequence of non-overlapping events is: \( [(09:00, 11:00), (11:00, 13:00), (13:00, 15:00)] \).

You are required to read the input from standard input (stdin) and produce the result to standard output (stdout).

inputFormat

The input begins with an integer (n) representing the number of events. The following (n) lines each contain two strings representing the start and end times of an event in 24-hour (HH:MM) format, separated by a space.

outputFormat

Output the longest sequence of non-overlapping events, with each event on a new line. Each line should display the start and end times of an event separated by a space.## sample

5
09:00 11:00
11:00 13:00
10:00 11:30
13:00 15:00
12:00 13:30

09:00 11:00
11:00 13:00
13:00 15:00

</p>