Do you think IIT Guwahati certified course can help you in your career?
Introduction
Hello Ninja, Welcome back to another problem. The Car Pooling problem is a classic optimisation problem in DSA that involves efficiently matching people who need to travel to the same destination.
We’ll go over all the methods, including brute force and the most efficient way to solve this problem.
Are you ready to go through this article?
Then let's start with the problem statement to think about the approaches for this problem.
Given a car with a certain capacity for empty seats, the vehicle can only drive in one direction, and initially, the car is at starting point. There is an array of trips, where each trip is represented by a list of 3 integers:
total_passengers: number of passengers for the trip.
start_from: the starting point of the trip, represented as the number of kilometres due from the car's starting point.
end_to: the ending point of the trip, represented as the number of kilometres due from the car's starting point.
The task is to determine if it is possible to pick up and drop off all passengers for all the given trips. The solution should return true if it is possible and false otherwise.
Example
trips = [[1, 1, 3], [2, 2, 6], [3, 5, 9]]
capacity = 5
Output = true
Explanation
So, on the first trip [1,1,3], one passenger travels from 1 to 3. From 2 two more passengers are added by the trip second [2,2,6], and the total passenger becomes 3. At 3 first trip ends, and the total number of passengers becomes 2. The number of passengers remained the same till 5 where 3 passengers added at 5 by trip third, so total passengers become 5. At 6 the second trip ends, and the total number of passengers becomes 3 and remains the same till 9.
Which follows the capacity of the car, which is 5.
Naive Approach
In this approach, we understand the problem with the example above. The problem requires us to determine if it is possible to pick up and drop off all passengers for all the given trips. To do this, we can simulate the trips and keep track of the number of passengers in the car at each point.
We start by initialising a variable to keep track of the current number of passengers in the car to 0. Then, we iterate through each trip and do the following for each trip. At any point in time when the total passengers are greater than capacity, return false and at the end, return true.
Algorithm
1.Declare anarray that stores the people still in the car for the journey.
2. Now run a loop for the trip length regarding the number of sub-trips in the trip list.
3. Iterate over the sub-trips and compute the number of people currently in the car with a total capacity.
4. If people number at any particular distance in a car greater than the capacity and how many sub-trips, we have to return the false otherwise, iterate over the loop.
5. We have to return true at the end. If the number of passengers never exceeds the capacity of the car during any point in the trip, return true.
C++ Code
#include <iostream>
#include <vector>
using namespace std;
bool car_Pooling(vector<vector<int>>& trips, int capacity) {
// Initialize an array of size 1001 with all elements as 0
int arr[1001] = {0};
// For each trip, add the number of passengers to the corresponding indices of the array
for(int i=0;i<trips.size();i++){
for(int j=trips[i][1];j<trips[i][2];j++){
arr[j] += trips[i][0];
if(arr[j] > capacity){
// If the number of passengers exceeds the capacity of the car at any point in the trip, return false
return false;
}
}
}
// If the number of passengers never exceeds the capacity of the car during any point in the trip, return true
return true;
}
int main() {
// Hardcoded input
vector<vector<int>> trips = {{1,1,3}, {2,2,6}, {3,5,9}};
int capacity = 5;
bool canTransport = car_Pooling(trips, capacity);
if(canTransport) {
cout << "All passengers can be transported" << endl;
} else {
cout << "Not all passengers can be transported" << endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
import java.util.*;
public class CodingNinjaSolution {
public boolean carPooling(int[][] trips, int capacity) {
// Initialize an integer array of size 1001 with all elements set to 0
int[] arr = new int[1001];
// For each trip, add the number of passengers to the corresponding indices of the array
for (int i = 0; i < trips.length; i++) {
for (int j = trips[i][1]; j < trips[i][2]; j++) {
arr[j] += trips[i][0];
if (arr[j] > capacity) {
// If the number of passengers exceeds the capacity of the car at any point in the trip, return false
return false;
}
}
}
// If the number of passengers never exceeds the capacity of the car during any point in the trip, return true
return true;
}
public static void main(String[] args) {
// Hardcoded input
int[][] trips = {{1,1,3}, {2,2,6}, {3,5,9}};
int capacity = 5;
// Create an instance of the CodingNinjaSolution class
CodingNinjaSolution solution = new CodingNinjaSolution();
// Call the carPooling function with the hardcoded input and print the result
boolean canTransport = solution.carPooling(trips, capacity);
if (canTransport) {
System.out.println("All passengers can be transported");
} else {
System.out.println("Not all passengers can be transported");
}
}
}
You can also try this code with Online Java Compiler
Now talking about the Complexity of the Code, As we have to iterate over the sub-trip present in the array, then we have the start and endpoint for the loop for which we are running for O(end point-start point) times and a trip for the length of trip, so its O(N^2) andSpace complexity is O(N) as for extra array for maintaining people strength in the car.
Greedy Approach
The Greedy approach to solve this problem involves sorting the trips array based on the start location, creating a priority queue to track current passengers in the car, and iterating over the trips array to remove passengers who have reached their destination, add new passengers to the car, and check if the car capacity is exceeded at any point.
Explanation
This is the explanation of the Greedy approach using the input trips = [[1, 1, 3], [2, 2, 6], [3, 5, 9]], capacity = 5:
Sort the trips array based on the start location of each trip: [[1, 1, 3], [2, 2, 6], [3, 5, 9]].
Create a priority queue (min-heap) to track the current passengers in the car, sorted by their end location. Initially, the queue is empty: queue = [].
Iterate over the sorted trips array:
Trip 1: queue = [(1, 3)], where (1, 3) represents one passenger with start location 1 and end location 3.
Trip 2: queue = [(1, 3), (2, 6)].
Trip 3: queue = [(1, 3)], since passenger (2, 6) is removed from the queue when its trip ends, and passenger (3, 9) is added to the queue under the capacity.
Since the car never has more than 5 passengers at any point in the trip, the function returns true.
Algorithm
Here is the algorithm for the above approach for solving the carpooling problem:
Sort the trips array based on the start location of each trip.
Create a priority queue to track the current passengers in the car.
Iterate over the trips array.
For each trip, remove any passengers who have completed their trips from the priority queue by checking if their end location is less than or equal to the current trip's start location, and add their capacity back to the car's total capacity.
Check if there is enough capacity in the car for the current trip. If not, return false.
If there is enough capacity, subtract the number of passengers for the current trip from the car's total capacity, and add the end location of the trip to the priority queue.
If all trips are completed, and the car has enough capacity for each trip, return true.
C++ Function
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
bool carPooling(vector<vector<int>>& trips, int capacity) {
// Sort trips based on start location
sort(trips.begin(), trips.end(), [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
});
// Create a priority queue to track current passengers
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// Iterate over trips and update priority queue
for (const auto& trip : trips) {
int num_passengers = trip[0];
int start_location = trip[1];
int end_location = trip[2];
// Remove passengers who have completed their trips
while (!pq.empty() && pq.top().first <= start_location) {
capacity += pq.top().second;
pq.pop();
}
// If there is not enough capacity for the current trip, return false
if (capacity < num_passengers) {
return false;
}
// Add current passengers to the priority queue
capacity -= num_passengers;
pq.push({end_location, num_passengers});
}
return true;
}
int main() {
// Hardcoded input
vector<vector<int>> trips = {{1,1,3}, {2,2,6}, {3,5,9}};
int capacity = 5;
bool result = carPooling(trips, capacity);
// Print result
if (result) {
cout << "It is possible to transport all passengers within the given capacity." << endl;
} else {
cout << "It is not possible to transport all passengers within the given capacity." << endl;
}
return 0;
}
You can also try this code with Online Java Compiler
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.AbstractMap;
public class CodingNinjaSolution {
public boolean carPooling(int[][] trips, int capacity) {
// Sort trips based on start location
Arrays.sort(trips, (a, b) -> Integer.compare(a[1], b[1]));
// Create a priority queue to track current passengers
PriorityQueue<AbstractMap.SimpleEntry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.getKey(), b.getKey()));
// Iterate over trips and update priority queue
for (int[] trip : trips) {
int numPassengers = trip[0];
int startLocation = trip[1];
int endLocation = trip[2];
// Remove passengers who have completed their trips
while (!pq.isEmpty() && pq.peek().getKey() <= startLocation) {
capacity += pq.poll().getValue();
}
// If there is not enough capacity for the current trip, return false
if (capacity < numPassengers) {
return false;
}
// Add current passengers to the priority queue
capacity -= numPassengers;
pq.offer(new AbstractMap.SimpleEntry<>(endLocation, numPassengers));
}
return true;
}
public static void main(String[] args) {
// Hardcoded input
int[][] trips = {{1,1,3}, {2,2,6}, {3,5,9}};
int capacity = 5;
CodingNinjaSolution s = new CodingNinjaSolution();
boolean result = s.carPooling(trips, capacity);
// Print result
if (result) {
System.out.println("It is possible to transport all passengers within the given capacity.");
} else {
System.out.println("It is not possible to transport all passengers within the given capacity.");
}
}
}
You can also try this code with Online Java Compiler
O(NlogN), where N is the number of elements in trips.
Reason: In the above code, The first operation in the code is sorting the trips based on the start location using sort() operation. This operation has a time complexity of O(n log n), where n is the number of trips.
Then, we iterate over each trip and perform several operations. The while loop that removes passengers who have completed their trips can run at most n times in the worst-case scenario, as each trip can have at most one passenger. The time complexity of the while loop is O(log n) for each iteration, as it requires removing the smallest element from the priority queue.
Space Complexity
O(N), where N is the number of elements in trips.
Reason: In the above code, we use a time vector of size 1001 to store the change in the number of passengers at each time. Hence, the space complexity is O(1001).
Prefix Sum Approach
We can optimize through the prefix sum method by keeping track of the total number of passengers at each location using a prefix sum array, which allows us to check if the number of passengers at any location exceeds the given capacity in constant time. This reduces the algorithm's time complexity from O(n log n) to O(n).
Dry Run
For the below example:
trips = {{1,1,3}, {2,2,6}, {3,5,9}};
capacity = 5;
We initialise the prefixSum array with 1001 elements, all set to 0.
We iterate over the trips array and update the prefix sum array as follows:
For the first trip {1,1,3}, we add one passenger to location 1 and subtract one passenger from location 3.
For the second trip {2,2,6}, we add two passengers to location 2 and subtract two passengers from location 6.
For the third trip {3,5,9}, we add three passengers to location 5 and subtract three passengers from location 9.
We iterate over the prefix sum array and keep track of the available capacity. At each location, we subtract the number of passengers from the capacity. If the capacity becomes negative at any point, we return false. Otherwise, we return true if we complete the iteration without hitting a negative capacity. Since the capacity never becomes negative from 1 to 9, we return true.
Implementation in C++
#include <iostream>
#include <vector>
using namespace std;
class CodingNinjaSolution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<int> prefixSum(1001, 0); // 1001 is the maximum possible end location
// Calculate the prefix sum of passengers at each location
for (auto& trip : trips) {
prefixSum[trip[1]] += trip[0];
prefixSum[trip[2]] -= trip[0];
}
// Iterate over the prefix sum and check capacity at each location
for (int i = 0; i < prefixSum.size(); i++) {
capacity -= prefixSum[i];
if (capacity < 0) {
return false;
}
}
return true;
}
};
int main() {
// Hardcoded input
vector<vector<int>> trips = {{1,1,3}, {2,2,6}, {3,5,9}};
int capacity = 5;
CodingNinjaSolution s;
bool result = s.carPooling(trips, capacity);
// Print result
if (result) {
cout << "It is possible to transport all passengers within the given capacity." << endl;
} else {
cout << "It is not possible to transport all passengers within the given capacity." << endl;
}
return 0;
}
Output
Java Implementation
public class CodingNinjaSolution {
public boolean carPooling(int[][] trips, int capacity) {
int[] prefixSum = new int[1001]; // 1001 is the maximum possible end location
// Calculate the prefix sum of passengers at each location
for (int[] trip : trips) {
prefixSum[trip[1]] += trip[0];
prefixSum[trip[2]] -= trip[0];
}
// Iterate over the prefix sum and check capacity at each location
for (int i = 0; i < prefixSum.length; i++) {
capacity -= prefixSum[i];
if (capacity < 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
// Hardcoded input
int[][] trips = {{1,1,3}, {2,2,6}, {3,5,9}};
int capacity = 5;
CodingNinjaSolution s = new CodingNinjaSolution();
boolean result = s.carPooling(trips, capacity);
// Print result
if (result) {
System.out.println("It is possible to transport all passengers within the given capacity.");
} else {
System.out.println("It is not possible to transport all passengers within the given capacity.");
}
}
}
You can also try this code with Online Java Compiler
In this method, we first create a frequency array freq of size 1001 (since the maximum value of any location in the problem is 1000), and initialize all elements of the array to 0. Then, we iterate over the trips array, add the number of passengers to freq[startLocation], and subtract the number of passengers from freq[endLocation]. This process updates the frequency array to keep track of the number of passengers at each location.
After updating the frequency array, we iterate over the array and calculate the prefix sum prefix[i] = prefix[i-1] + freq[i] for each index i. This prefix sum array keeps track of the number of passengers up to each location.
Finally, we iterate over the prefix array and check if the number of passengers at any location exceeds the given capacity. If so, we return false, indicating that it is not possible to transport all passengers within the given capacity. Otherwise, we return true.
Complexity
Time complexity
O(n), where n is the number of trips.
Reason: Since we iterate over the trips array, the prefix array, and the freq array once. So complexity is O(n). Therefore, this method is more efficient than the priority queue method, which has a time complexity of O(n log n) due to the use of a priority queue.
Space complexity
O(1)
Reason: we create a frequency array freq of size 1001 to keep track of the number of passengers at each location. We also create a prefix sum array prefix of the same size to keep track of the total number of passengers up to each location. Both arrays have a constant size of 1001, regardless of the number of trips or the capacity. Therefore, the space complexity of this method is O(1).
Frequently Asked Questions
What is pre-computation in Problem-solving?
We find some important points and use them in solving the questions.
What are some applications of the carpooling problem in real-world scenarios?
The carpooling problem has applications in various real-world scenarios, such as ride-sharing platforms, transportation planning, and public transit optimisation. It is also relevant to the management of corporate carpooling programs, school transportation systems, and on-demand transportation services.
How does a Priority Queue differ from a regular Queue?
The main difference between a Priority Queue and a regular Queue is that a Priority Queue prioritizes elements based on their priority value, while a regular Queue serves elements in the order they were added. In a Priority Queue, elements with higher priority are served before elements with lower priority, regardless of the order in which they were added.
What is the Time Complexity of the Naive approach?
Time Complexity is O(N^2), and Space Complexity is O(N).
What operations can be performed on a Priority Queue?
The most common operations that can be performed on a Priority Queue include inserting an element with a priority value, removing the element with the highest priority, and peeking at the element with the highest priority without removing it. Some Priority Queue implementations may also support updating the priority of an element and merging two Priority Queues.
Conclusion
In this, we learn that one of the concepts used for solving the problem is pre-computation and how to apply that in solving the problem. For taking the example of it, we can see in the problem that we need to compare with the capacity of the person currently in the car, so for the sake of convenience for repeated calculation, we directly store the current people in the car for particular kilometres in the form of an array, which also helps to optimise the code by reducing the steps of calculation with reducedTime Complexity, from their idea of Pre-computation developed.
In general, we apply it when we perform the same task. For the next part, we also need to calculate the previous, so we do Pre-computation, which often reduces the time of calculation and complexity of the problem ofData Structure.
84+ registered 