All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Minimum Cabs
Tag(s):

Algorithms, Easy, 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

IndiaHacks 2017: Programming [Wildcard]

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?