PROBLEM LINK:
Contest link
Problem link
Practice link
Author: HITK Chapter
Tester: Ankur Kayal
Editorialist: HITK Chapter
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Greedy, 2-Pointers.
PROBLEM:
Given the list of entry and exit stops of n passengers, you have to calculate the minimum number of bogies the train should have initially if each bogie can accommodate a maximum of k passengers.
QUICK EXPLANATION:
Store the entry and exit times in a list of pairs. After sorting the list, simply iterate the list to store the maximum number of passengers present on the train at any moment.
EXPLANATION:
So, as given in the problem, there are several stops on the train route at which some people leave the train and some board the train. What we can do is store all the boarding and exit times of each person in a list of pairs along with 1 or -1, such that -1 indicating that the person left the train at that stop and +1 indicating the person entered the train at that stop.
Now after sorting the list, we will get a list of times from the initial point. Now we can maintain a counter and simply transverse the list to check the number of people present on the train at that particular time.
If the second element of pair is -1, decrease the counter by 1 (that means that passenger left the train and the count of people present in the train at that particular time decreases by 1) and similarly, if the second element of pair is +1, increase the count by 1. (Note that if at any particular stop, if there are both operations, i.e some people are leaving and some are entering, then we will perform the exit operation first, then the entry operation will be performed, sorting the list of pairs will take care of this).
Now finally we will get the count of the max number of passengers present on the train at any particular time, dividing it by k and taking its ceil will give us the minimum number of bogies that will be required.
Time Complexity : O(nlog(n)) for each test case
Alternate Solution:
This problem can also be done using 2 pointers. Store the entry and exit times in 2 separate arrays and use 2 pointers i & j for iterating each array. Store the count of passengers at each point of time during iteration.