Last Updated: 26 Apr, 2021
Carnival With Friends
Hard
Asked in company
India’s one of the most prominent and much-awaited Surajkund Mela in Haryana has started. Ninja and his ‘K’ friends are going to this carnival. This carnival has an ‘N’ number of amusement rides lined up and each ride’s starting and finishing time is given on the visiting card. What is the maximum total number of rides can the friends take if they act optimally?
For example :
If ‘N’ = 3 and ‘K’ = 2, and the [‘startTime’ , ‘endTime’] of the 3 rides are [0,2],[1,3],[2,4]
Then the 2 friends can attend all the 3 rides as follows:
Friend 1 will attend ride [0,2] at t = 0
Friend 2 will attend ride [1,3] at t = 1
Friend 1 will be free at t = 2, and will now attend ride [2,4] at t = 2
Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then ‘T’ test cases follow:
The first line of each test case has 2 space-separated integers ‘N’ and ‘K’, where ‘N’ is the number of rides given and ‘K’ is the number of friends.
Following ‘N’ lines of each test case have 2 space-separated integers, ‘startTime’ and ‘endTime’ of each ride.
Output Format :
For each test case, print an integer denoting the maximum number of rides the Ninja's friends can attend.
Output for every test case will be printed in a separate line.
Note :
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= K <= N <= 10 ^ 5
0 <= startTime <= endTime <= 10 ^ 9
Where ‘startTime’ is the starting time of a ride and ‘endTime’ is the ending time of the ride.
Time limit: 1 sec
Approaches
The idea is to first sort the rides in ascending order according to their ‘endTime’. This is done so that when a friend wants to attend a ride, he’s given the ride which will end the earliest so that he is free at the earliest time.
Then, for each ride, we will try to find a friend who is available to attend that ride and was freed at the latest so that other friends who were freed before him are available to attend later ride (which may have a starting time lesser than the current ride).
carnivalRides(‘N’, ‘K’, ‘rides’):
Here, ‘N’ is the number of rides available, ‘K’ is the number of friends and ‘rides’ is the array/list that stores ‘startTime’ and ‘endTime’ of all the ‘N’ rides, so ‘rides[i]’ = [‘start time of ride i’ , ‘end time of ride i’].
Here is the algorithms:
- Sort ‘rides’ according to the ‘endTime’ of each ride.
- Use a data structure (say ‘abc’) in which data is always sorted after insertion or deletion and duplicates can be present. Create object ‘free_time’ of ‘abc’ which will store the time at which each of the ‘K’ friends is freed after a ride.
- Initialize variable ‘ans’ = 0, this will store the maximum number of rides that can be taken.
- Run a for loop from 0 to ‘K’ (say iterator = ‘i’):
- Insert 0 in ‘free_time’ which will denote that the ‘ith’ friend will be freed at time ‘t’ = 0. (this is done because initially all the friends are free).
- Run a for loop from 0 to ‘N’ (say iterator = ‘i’) (to determine if a ride can be taken or not):
- Iterator ‘nextGreaterIndex’ = ‘free_time.binarySearch(ride[i][0])’. Here, ‘free_time.binarySearch(ride[i][0])’ will return an index of the next greater number than the ‘start time’ of ‘ride[i]’ from ‘free_time’.
- If 'nextGreaterIndex' is equal to the beginning of ‘free_time’, that means no friend is free before ‘startTime’ of ‘ride[i]’, then:
- Continue.
- Move 'nextGreaterIndex' to the previous index of ‘free_time’ (i.e 'nextGreaterIndex' is equal to 'nextGreaterIndex' - 1) so that we find the latest time at which a friend is freed just before or at ‘startTime’ of ‘ride[i]’.
- Delete the time at index 'nextGreaterIndex' from ‘free_time’. This means a friend (say ‘currFriend’) who has freed at time ‘free_time['nextGreaterIndex]’ is no longer free.
- Insert time ‘ride[i][1] (i.e ‘end time’ of ride ‘i’) into ‘free_time’. This means ‘currFriend’ will now be freed at ‘ride[i][1]’.
- ‘ans’ = ‘ans’ + 1.
- Return ‘ans’.