Car Pooling
Car Pooling is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Line Sweep subpattern.
Problem statement
Implement Solution.carPooling to determine whether one vehicle can complete every requested trip while respecting its passenger capacity. The vehicle travels only east, so locations are ordered along a single route.
Each element of trips is a three-integer list [numPassengers, from, to]. numPassengers people board at location from and leave at location to; from is strictly less than to. Passengers leaving at a location do so before passengers scheduled to board there, so they do not occupy seats together at that exact transition.
Return true if the vehicle's passenger count never exceeds capacity during the route. Return false as soon as any location would require more than capacity seats.
Example 1:
Input: trips = [[3,0,4],[2,3,7]], capacity = 4 Output: false Explanation: Between locations 3 and 4, five passengers are aboard at once, which is more than the capacity of four.
Example 2:
Input: trips = [[2,1,5],[3,5,8],[1,0,2]], capacity = 3 Output: true Explanation: The first and third trips overlap for two passengers, and the second trip starts exactly when the first ends, so the passenger count never exceeds three.
Example 3:
Input: trips = [[4,2,6],[1,4,9],[2,0,3]], capacity = 5 Output: false Explanation: From location 4 to location 6, all five passengers from the first two trips are aboard, and the two passengers from the third trip are still aboard until location 3 only; the count reaches five, so this case is actually within capacity? No—at location 2 to 3 the count is six, exceeding five.
Constraints:
- 1 <= trips.length <= 1000 - Each element of trips contains exactly 3 integers - 1 <= trips[i][0] <= 100 - 0 <= trips[i][1] < trips[i][2] <= 1000 - 1 <= capacity <= 10^5 - The vehicle travels only east, and every trip satisfies from < to
Topics and companies
Topics: Array, Greedy, Line Sweep, Prefix Sum.
How to practise Car Pooling on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(trips.length + 1000) time and O(1000) space.
Open Car Pooling in the code editor, or read the Car Pooling editorial for a worked solution with its approach and complexity analysis.
Where Car Pooling sits in the DSA pattern sheet
- Greedy Patterns pattern guide
- Line Sweep subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Car Pooling
Other problems that use the same Line Sweep and Greedy Patterns techniques:
- Employee Free Time — Hard, same subpattern
- Interval List Intersections — Medium, same subpattern
- Partition Labels — Medium, same subpattern
- Assign Cookies — Easy, same pattern
- Candy — Hard, same pattern
- Distant Barcodes — Medium, same pattern