Found This Question on One of the Forum :D & posting here as thought it seems to be something interesting :) There is a list containing the checkin and checkout time of every person in a party . The checkin time is in ascending order while the checkout is random .
Eg:
Check_in Check_out
Person 1 8.00 9.00
Person 2 8.15 8.30
Person 3 8.30 9.20
and so on ...Now , give an optimized solution to find at what time the maximum number of people will be in the party .
Algorithm
It has the same Algorithm That We have been used to solve Bus-Station Problem :)
Algorithm
It has the same Algorithm That We have been used to solve Bus-Station Problem :)
Time Compelxity O(nlogn)
Space Complexity O(1)
3 comments :
Hi Shashank,
Can i have an Array(hashtable) where indexes for each 5 mins from 8pm to 10pm initializing with zeros
And now scan all the three schedules and add 1 in the corresponding 5min index in the array now u have number of people in the corresponding 5 min.
I just solved it with a bit different approach.
Now i am using a Linked List. Each node Corresponds to an event
Event= Check In/CheckOut
Value of each node = Number of participants in the party
Sort all the events(Check In and Check Out)
So lets start
Event 1. Check In 8:00 Count = 1.
Event 2. Check In 8:15 count = 2.
Event 3. 8:30 Check Out + Checke In = 2
Event 4. 9:00 Check Out = 1
Event 5. 9:20 check out = 0.
Now we have 5 nodes corresponding to all events Scan twice all the nodes we can get what was the max freq and at what interval
@anshul..You are very much right,i have also mentioned two similar problem with same algorithm , also give me some time to reply back for your other comments , keep it up :)
Cheers !!!
Shashank
Post a Comment