All Tracks>Algorithms> Greedy Algorithms> Basics of Greedy Algorithms> Problem
Minimum Cabs
★★★★★

4

43 votes
Algorithms, Easy, Greedy Algorithms
Problem

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 denoting the number of persons. Next N lines contains 4 integers, and , () (), denoting the start time () and end time (). 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
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation


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.

Contributers:
Editor Image

?