SOLVE

LATER

Minimum Cabs

/

Assume there are *N* persons and each person needs exactly one cab. For each person, you are given the start time and end time (both inclusive) during which that person will travel. Find the minimum number of cabs required.

**Input:**

First line contains an integer, *N* \((1 \le N \le 10^5)\) denoting the number of persons. Next *N* lines contains *4* integers, \(HH1, MM1, HH2\) and \(MM2\), (\(0 \le HH1, HH2 \le 23\)) (\(0 \le MM1, MM2 \le 59\)), denoting the start time (\(HH1:MM1\)) and end time (\(HH2:MM2\)). It is guaranteed that start and end time will not span midnight.

**Output:**

Print the minimum number of cabs required.

Explanation

\(N = 6\)

Start and end time of *N* persons are:

- 01:00 - 02:00 - He will use first cab.
- 16:00 - 21:30 - He will use first cab since the first cab is free in this time period.
- 09:30 - 13:00 - He will use first cab.
- 21:30 - 22:30 - He will use second cab since the second person is using the first cab.
- 21:30 - 22:30 - He will use third cab since the second and fourth person are using the first and second cab.
- 12:00 - 12:30 - He will use second cab since the third person is using the first cab.

So, we need only *3* cabs.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...