There is a car with no. of empty seats equal to the given capacity. The vehicle only drives in a particular direction (i.e., it cannot turn around and go to another direction). Given the integer capacity and an array of trips[] where trips[i] = [num_Passengers, start_loc, end_loc] indicates that the ith trip has num_Passengers (1 <= num_passengers <= 108) passengers and the locations to pick them up and drop them off are start_loc and end_loc
(0 <= start_loc, end_loc <= 103) respectively, the task is to return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.
Examples:
Input: trips[] = [[3, 2, 7], [3, 7, 9], [8, 3, 9]], capacity = 11
Output: True
Explanation: First from locations 2 to 7 there will be three passengers in the car and after reaching 7 location they will take off, and then from 7 to 9 will be three passengers will travel in the car but the last trip from 3 to 9 will have 8 passengers and the capacity is 11. So, at 7 locations 3 passengers will take off according to the first trip and 7 to 9 new three passengers will travel. So, 8+3 = 11. The capacity of 11 will be maintained.Input: trips[] = [[2, 1, 5], [3, 3, 7]], capacity = 5
Output: True
Explanation: First from locations 1 to 5 there will be 2 passengers in the car and after reaching 5 locations they will take off, and then from 3 to 7 will be 3 passengers will travel in the car but at most there will be 5 passengers in the car between location 3 to 5. So, The capacity of 5 will be maintained.
Approach: To solve the problem follow the below idea:
The prefix sum approach is a method that aims to keep track of the number of passengers at locations, along a route. It uses a technique called prefix sums to calculate the passenger count at each location. This is done by incrementing the count when passengers are picked up and decrementing it when passengers are dropped off. By checking the capacity of the car at each location this approach determines whether it’s possible to complete all trips within the specified capacity.
To solve the problem follow the below steps:
- Start by initializing an array called “prefixSum” with a size of 1001 representing the end location. Set all elements in this array to 0.
- Iterate through each trip:
- For each trip add the number of passengers to the starting location in the “prefixSum” array and Subtract the number of passengers from its ending location.
- Traverse through the “prefixSum” array.
- For each location deduct its value from the cars capacity.
- If at any point during this traversal the capacity becomes negative return false as it indicates a violation of capacity.
- If you complete traversing through all locations without encountering any violations return true.
- This approach allows for tracking and calculation of passenger counts along locations, on a route while considering car capacity limitations.
Below is the C++ implementation of above approach:
C++
// C++ code for the above approach:#include <iostream>#include <vector>using namespace std;bool CarPooling(vector<vector<int> >& trips, int occupancy){ vector<int> prefixSum(1001, 0); // 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++) { occupancy -= prefixSum[i]; if (occupancy < 0) { return false; } } return true;}// Drivers codeint main(){ vector<vector<int> > trips = { { 3, 2, 7 }, { 3, 7, 9 }, { 8, 3, 9 } }; int occupancy = 11; bool result = CarPooling(trips, occupancy); // Print result if (result) { cout << "True" << endl; } else { cout << "False" << endl; } vector<vector<int> > trips2 = { { 2, 1, 5 }, { 3, 3, 7 } }; int occupancy2 = 5; bool result2 = CarPooling(trips2, occupancy2); // Print result if (result2) { cout << "True" << endl; } else { cout << "False" << endl; } return 0;} |
Java
// Java code for the above approach:import java.util.Arrays;import java.util.List;public class CarPooling { public static boolean carPooling(List<List<Integer>> trips, int occupancy) { int[] prefixSum = new int[1001]; // Calculate the prefix sum of passengers at each location for (List<Integer> trip : trips) { prefixSum[trip.get(1)] += trip.get(0); prefixSum[trip.get(2)] -= trip.get(0); } // Iterate over the prefix sum and check capacity at each location for (int i = 0; i < prefixSum.length; i++) { occupancy -= prefixSum[i]; if (occupancy < 0) { return false; } } return true; } public static void main(String[] args) { List<List<Integer>> trips1 = Arrays.asList( Arrays.asList(3, 2, 7), Arrays.asList(3, 7, 9), Arrays.asList(8, 3, 9) ); int occupancy1 = 11; boolean result1 = carPooling(trips1, occupancy1); // Print result if (result1) { System.out.println("True"); } else { System.out.println("False"); } List<List<Integer>> trips2 = Arrays.asList( Arrays.asList(2, 1, 5), Arrays.asList(3, 3, 7) ); int occupancy2 = 5; boolean result2 = carPooling(trips2, occupancy2); // Print result if (result2) { System.out.println("True"); } else { System.out.println("False"); } }}//this code is contributed by uttamdp_10 |
Python3
# Python code for the above approach:# Function to check if carpooling is possibledef carpooling(trips, occupancy): prefix_sum = [0] * 1001 # Calculate the prefix sum of # passengers at each location for trip in trips: passenger_count, start_location, end_location = trip prefix_sum[start_location] += passenger_count prefix_sum[end_location] -= passenger_count # Iterate over the prefix sum and # check capacity at each location for count in prefix_sum: occupancy -= count if occupancy < 0: return False return True# Driver codetrips = [[3, 2, 7], [3, 7, 9], [8, 3, 9]]occupancy = 11result = carpooling(trips, occupancy)# Print resultif result: print("True")else: print("False")trips2 = [[2, 1, 5], [3, 3, 7]]occupancy2 = 5result2 = carpooling(trips2, occupancy2)# Print resultif result2: print("True")else: print("False") |
C#
using System;using System.Collections.Generic;class Program{ static bool CarPooling(List<List<int>> trips, int occupancy) { List<int> prefixSum = new List<int>(1001); // Initialize prefixSum list with 0s for (int i = 0; i < 1001; i++) { prefixSum.Add(0); } // Calculate the prefix sum of passengers // at each location foreach (var trip in trips) { prefixSum[trip[1]] += trip[0]; prefixSum[trip[2]] -= trip[0]; } // Iterate over the prefix sum and check // capacity at each location foreach (var value in prefixSum) { occupancy -= value; if (occupancy < 0) { return false; } } return true; } static void Main() { List<List<int>> trips = new List<List<int>>() { new List<int>{3, 2, 7}, new List<int>{3, 7, 9}, new List<int>{8, 3, 9} }; int occupancy = 11; bool result = CarPooling(trips, occupancy); // Print result if (result) { Console.WriteLine("True"); } else { Console.WriteLine("False"); } List<List<int>> trips2 = new List<List<int>>() { new List<int>{2, 1, 5}, new List<int>{3, 3, 7} }; int occupancy2 = 5; bool result2 = CarPooling(trips2, occupancy2); // Print result if (result2) { Console.WriteLine("True"); } else { Console.WriteLine("False"); } }} |
Javascript
// JavaScript code for the above approach:function carPooling(trips, occupancy) { const prefixSum = new Array(1001).fill(0); // Calculate the prefix sum of passengers at each location for (const trip of trips) { prefixSum[trip[1]] += trip[0]; prefixSum[trip[2]] -= trip[0]; } // Iterate over the prefix sum and check capacity at each location for (let i = 0; i < prefixSum.length; i++) { occupancy -= prefixSum[i]; if (occupancy < 0) { return false; } } return true;}// Drivers codeconst trips1 = [[3, 2, 7], [3, 7, 9], [8, 3, 9]];const occupancy1 = 11;const result1 = carPooling(trips1, occupancy1);// Print resultif (result1) { console.log("True");} else { console.log("False");}const trips2 = [[2, 1, 5], [3, 3, 7]];const occupancy2 = 5;const result2 = carPooling(trips2, occupancy2);// Print resultif (result2) { console.log("True");} else { console.log("False");} |
True True
Time Complexity: O(N), where N is the number of elements in trips.
Auxiliary Space: O(1), where N is the number of elements in trips.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
