Maximum Rental Scheduling

Given a list of rental requests, each with a start and end time in HH:MM format, determine the maximum number of non-overlapping rental intervals that can be scheduled in a day.

Two intervals are considered non-overlapping if the start time of an interval is greater than or equal to the end time of the previously scheduled interval. Formally, if we denote a rental as a pair \((s, t)\) (with times in \(HH:MM\) 24-hour format), then a new rental \((s', t')\) can be scheduled after \((s, t)\) if and only if \(s' \ge t\).

For example, if an interval ends at \(10:00\) and another starts at \(10:00\), they do not overlap.

inputFormat

The first line contains an integer \(n\) representing the number of rental requests. Each of the following \(n\) lines contains two time stamps in the HH:MM format separated by a space, indicating the start and end times of a rental request.

outputFormat

Output a single integer representing the maximum number of non-overlapping rental intervals that can be scheduled in a day.

4
09:00 10:00
10:00 11:00
11:00 12:00
09:30 10:30

3