All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Minimum Cabs
/

Algorithms, Greedy algorithm

Problem
Editorial
Analytics

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.

SAMPLE INPUT
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
SAMPLE OUTPUT
3
Explanation

\(N = 6\)
Start and end time of N persons are:

  1. 01:00 - 02:00 - He will use first cab.
  2. 16:00 - 21:30 - He will use first cab since the first cab is free in this time period.
  3. 09:30 - 13:00 - He will use first cab.
  4. 21:30 - 22:30 - He will use second cab since the second person is using the first cab.
  5. 21:30 - 22:30 - He will use third cab since the second and fourth person are using the first and second cab.
  6. 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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?