Non-overlapping Conference Room Bookings

Given a list of booking intervals for a conference room over one or multiple days, your task is to determine the maximum number of non-overlapping bookings that can be accommodated for each day.

Each test case starts with an integer n (number of bookings) followed by n lines. Each line contains two times in HH:MM format representing the start and end time of a booking. The input terminates when a test case starts with 0.

A booking i with start time \( s_i \) and end time \( e_i \) can be selected if and only if its start time satisfies the condition \( s_i \geq e_{prev} \) where \( e_{prev} \) is the end time of the last selected booking. Use a greedy algorithm by sorting the bookings by their end time.

inputFormat

The input consists of multiple test cases. Each test case begins with an integer n (n ≥ 0) on a line, indicating the number of bookings for that day. This is followed by n lines, each containing two strings representing the start and end times in HH:MM format. The input terminates when a test case starts with a line containing a single 0. All input should be read from standard input (stdin).

outputFormat

For each test case (day), output a single line containing a single integer — the maximum number of non-overlapping bookings that can be scheduled for that day. Output each result on a new line to standard output (stdout).## sample

3
09:00 11:00
13:00 15:00
10:00 12:00
0

2