Carnival With Friends

Hard
0/120
Average time to solve is 45m
profile
Contributed by
6 upvotes
Asked in company
Microsoft

Problem statement

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
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
3 2
2 5
2 3
1 2
Sample Output 1 :
3
Explanation of Sample Input 1 :
In the first test case, ‘N’ = 3 and ‘K’ = 2, and the [‘startTime’ , ‘endTime’] of the 3 rides are [1, 2] , [2, 3] , [2, 5]. Then the 2 friends can attend all the 3 rides as follows:
Friend 1 will attend ride [1, 2] at t = 1
Friend 2 will attend ride [2, 3] at t = 2
Friend 1 will be free at t = 2, and will now attend ride [2, 5] at t = 2
Sample Input 2 :
1
4 2
2 12
0 3
1 2
2 4
Sample Output 2 :
3
Explanation of Sample Input 2 :
In the first test case,  ‘N’ = 4 and ‘K’ = 2, and the [‘startTime’ , ‘endTime’] of the 3 rides are [2, 12] , [0, 3] , [1, 2] , [2, 4]. Then the 2 friends can attend 3 rides as follows:
Friend 1 will attend ride [0, 3] at t = 0
Friend 2 will attend ride [1, 2] at t = 2
Friend 2 will be free at t = 2, and will now attend ride [2, 4] at t = 2, but friend 1 will not be able to attend the remaining ride [2, 12] because its ‘start time’ is 2 and he will be free at 3.
Hint

Can you search which friends are free to attend a specific ride?

Approaches (1)
Sorting and searching (Greedy)

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:

 

  1. Sort ‘rides’ according to the ‘endTime’ of each ride.
  2. 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.
  3. Initialize variable ‘ans’ = 0, this will store the maximum number of rides that can be taken.
  4. 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).
  5. 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.
  6. Return ‘ans’.
Time Complexity

O(N * log(N)), where ‘N’ is the number of rides given and ‘K’ is the number of friends.

 

Sorting the array ‘rides’ will take O(N * log(N)) time, creating object of data structure ‘abc’ named ‘free_time’ of ‘K’ size will take O(K * log(K)) time, Iterating ‘rides’ and during each iteration, searching in ‘free_time’ using binary search will take O(N  *log(K)) time. Hence, total time = O(N * log(N) + K * log(K) + N * log(K)) which is approximately equal to O(N * log(N)).

Space Complexity

O(K), where  ‘K’ is the number of friends.

 

Creating an object of data structure ‘abc’ of size ‘K’ will take ‘K’ time complexity.

Code Solution
(100% EXP penalty)
Carnival With Friends
Full screen
Console