This page is still under construction.

Parts of this page are still being built. What you see may change.

Bus Terminal

Interview

Time limit1sMemory limit1024 MB

Summary
Given N bus arrival and departure times, find the minimum number of service spaces so that no bus ever has to wait, with departures processed before simultaneous arrivals.
Level

Medium4 of 10

Topics
Sorting, Intervals, Greedy, Implementation
Solved
No attempts yet

Problem

Buses that have finished their routes arrive at the terminal. A bus that arrives at the terminal enters a spot where it is serviced. That is, if 4 buses are at the terminal, at least 4 spaces for servicing buses are needed. If bus A is arriving at the terminal and bus B is departing the terminal at the same time, bus B departs first, and then bus A arrives.

The bus timetable is the same every day, and the arrival and departure times at the terminal are the same every day.

The bus timetable has now changed, so the minimum number of spaces needed to service buses must be recalculated. Help with this calculation.

Input

The first line gives the number of buses NN arriving at the terminal.

From the second line to the N+1N+1-th line, the arrival time and departure time of each bus are given. A bus's departure time is later than its arrival time.

Times are given in the format HH:MM:SS.sss, where HH is hours, MM is minutes, SS is seconds, and sss is milliseconds.

Output

Output the minimum number of spaces needed to service buses.

Constraints

  • 1≤N≤100,0001 ≤ N ≤ 100,000
  • 0≤HH<240 ≤ HH < 24
  • 0≤MM<600 ≤ MM < 60
  • 0≤SS<600 ≤ SS < 60
  • 0≤sss<10000 ≤ sss < 1000

Examples1

  1. Example 1

    Input
    4
06:00:00.000 06:30:00.000
06:10:45.000 06:15:00.000
06:30:00.000 06:40:00.000
06:01:00.001 06:40:00.001
    Expected output
    3