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.
6 1 0 2 0 16 0 21 30 9 30 13 0 21 30 22 30 21 30 22 30 12 0 12 30
3
\(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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor