Last Updated: 11 Apr, 2021
Car Pooling
Moderate
Asked in companies
You are working as a cab driver. Your car moves in a straight line and moves toward the forward direction only. Initially, you have ‘C’ empty seats for the passengers.
Now, you are given ‘N’ number of trips that you have to make. In each trip, you are given three integers ‘Num’, ‘pickPoint’, and ‘dropPoint’ denoting that there are ‘Num’ numbers of passengers standing at 'pickpoint’ and you have to drop them at 'droppoint’.
Your task is to find if it is possible to pick up and drop off all the passengers of all the given trips or not.
Note :
You have a special type of car containing any number of seats.
Input Format :
The first line contains a single integer ‘T’, denoting the number of test cases.
Each test case’s first line contains ‘C’ and ‘N’, denoting the car’s capacity and the number of trips you have to make.
The next ‘N’ lines contain 3 integers, each denoting the number of passengers, pick up point, and drop point of the trip respectively.
Output Format :
For each test case, print “True” if possible to make the trip and “False” otherwise.
Print the output of each test case in a separated line.
Note :
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
1 <= C <= 10^5
1 <= N <= 10^3
0 <= passengers <= 100
0 <= pickPoint, dropPoint <= 1000
Where ‘T’ is the number of test cases, ‘C’ is the car’s capacity, and “N’ is the number of trips you have to make.
Time limit: 1 sec.
Approaches
The simple idea is that we will keep a record of the number of passengers changed at every time in a hash map ‘passengers’ where the key represents the time at which the number of passengers changed and the value at that key represents the count of passengers changed.
For Example- If we have trips = [ 2, 1,4 ], [ 2, 2,5 ] then at time = 1, no of passengers changed and increased by 2. So passengers[ 1 ] = 2. At time = 4, these passengers reach their destination so at time = 4, no of passengers get reduced by 2. So passengers[ 4 ] = -2.
Similarly passengers[ 2 ] = 2 and passengers[ 5 ] = -2.
In the hash map, we will increment the value at the pickup point of the ‘i-th’ trip and decrement the value at the drop point of the ‘i-th’ trip by the number of passengers in the ‘i-th’ trip.
As in the hash map, keys are stored in sorted order. So adding the values of this hash map will give the number of passengers at every key time. If no of the passengers exceeds the capacity of the car at any time, we will return false.
Algorithm
- Initialize a hash map ‘passengers’ that maps from integer to integer.
- Run a loop i: 0 to N - 1 to check every trip detail.
- Increment passengers[ trip[ i ][ 1 ] ] by trip[ i ][ 0 ].
- Decrement Passengers[ trip[ i ][ 2 ] ] by trip[ i ][ 0 ].
- Traverse through the hash map.
- Store the sum of values of the hash map in a variable ‘count’.
- If count > C( capacity ), return false.
- Return true.
The range for staring and ending location varies from 0 to 1000 which is not a large range.
We will solve the problem as we did in the previous approach, but instead of using a hash map, we will take a 1-D array ‘passengers’ where passengers[ i ] denotes the number of passengers changed at ‘i-th’ time.
By doing this, we can update every trip detail in a constant time which was taking (log(N)) time in case of hash map.
Algorithm
- Initialize a 1-D array ‘passengers’ of size ‘1001’ with all values ‘0’.
- Run a loop i: 0 to N - 1 to check every trip detail.
- Increment passengers[ trip[ i ][ 1 ] ] by trip[ i ][ 0 ].
- Decrement Passengers[ trip[ i ][ 2 ] ] by trip[ i ][ 0 ].
- Initialize a variable ‘count’ with the value ‘0’.
- Traverse through the ‘passengers’ array, i: 0 to 1000
- Increment ‘count’ by passengers[ i ].
- If count > C, return false.
- Return true.