Car Pooling Problem

Problem

There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).

You are given the integer capacity and an array trips where trips[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi respectively. The locations are given as the number of kilometers due east from the car’s initial location.

Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.

Examples

Example 1:

1
2
3
4


Input:
trips = [[2,1,5],[3,3,7]], capacity = 4
Output:
 false

Example 2:

1
2
3
4


Input:
trips = [[2,1,5],[3,3,7]], capacity = 5
Output:
 true

Solution

Method 1 – Prefix Sum (Difference Array)

Intuition

The key idea is to track the net change in the number of passengers at each location using a difference array or map. For every trip, we increase the passenger count at the pickup point and decrease it at the drop-off point. By sweeping through the locations in order, we can efficiently check if the number of passengers ever exceeds the car’s capacity.

Approach

Record Changes:
- For each trip, add the number of passengers at the pickup location and subtract them at the drop-off location in a map or array.
Sweep Through Locations:
- Iterate through the locations in order, maintaining a running total of passengers in the car.
- If at any point the running total exceeds the car’s capacity, return false.
Return Result:
- If the capacity is never exceeded, return true.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


#include <map>
using namespace std;
class Solution {
public:
	bool carPooling(vector<vector<int>>& trips, int cap) {
		map<int, int> m;
		for (auto& t : trips) {
			m[t[1]] += t[0];
			m[t[2]] -= t[0];
		}
		int cur = 0;
		for (auto& [_, v] : m) {
			cur += v;
			if (cur > cap) return false;
		}
		return true;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func carPooling(trips [][]int, cap int) bool {
	m := map[int]int{}
	for _, t := range trips {
		m[t[1]] += t[0]
		m[t[2]] -= t[0]
	}
	keys := []int{}
	for k := range m { keys = append(keys, k) }
	sort.Ints(keys)
	cur := 0
	for _, k := range keys {
		cur += m[k]
		if cur > cap { return false }
	}
	return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
	public boolean carPooling(int[][] trips, int cap) {
		TreeMap<Integer, Integer> m = new TreeMap<>();
		for (int[] t : trips) {
			m.put(t[1], m.getOrDefault(t[1], 0) + t[0]);
			m.put(t[2], m.getOrDefault(t[2], 0) - t[0]);
		}
		int cur = 0;
		for (int v : m.values()) {
			cur += v;
			if (cur > cap) return false;
		}
		return true;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
	fun carPooling(trips: Array<IntArray>, cap: Int): Boolean {
		val m = sortedMapOf<Int, Int>()
		for (t in trips) {
			m[t[1]] = m.getOrDefault(t[1], 0) + t[0]
			m[t[2]] = m.getOrDefault(t[2], 0) - t[0]
		}
		var cur = 0
		for (v in m.values) {
			cur += v
			if (cur > cap) return false
		}
		return true
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
	def carPooling(self, trips: list[list[int]], cap: int) -> bool:
		m = {}
		for num, start, end in trips:
			m[start] = m.get(start, 0) + num
			m[end] = m.get(end, 0) - num
		cur = 0
		for k in sorted(m):
			cur += m[k]
			if cur > cap:
				return False
		return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


use std::collections::BTreeMap;
impl Solution {
	pub fn car_pooling(trips: Vec<Vec<i32>>, cap: i32) -> bool {
		let mut m = BTreeMap::new();
		for t in &trips {
			*m.entry(t[1]).or_insert(0) += t[0];
			*m.entry(t[2]).or_insert(0) -= t[0];
		}
		let mut cur = 0;
		for v in m.values() {
			cur += v;
			if cur > cap { return false; }
		}
		true
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


function carPooling(trips: number[][], cap: number): boolean {
	const m: Record<number, number> = {};
	for (const [num, start, end] of trips) {
		m[start] = (m[start] || 0) + num;
		m[end] = (m[end] || 0) - num;
	}
	let cur = 0;
	for (const k of Object.keys(m).map(Number).sort((a, b) => a - b)) {
		cur += m[k];
		if (cur > cap) return false;
	}
	return true;
}

Complexity

⏰ Time complexity: O(n log n), where n is the number of trips. We sort the unique locations and process each trip once.
🧺 Space complexity: O(n), for storing the changes at each location.

Method 2 – Min-Heap for Ongoing Trips

Intuition

We can efficiently track ongoing trips by sorting all trips by their start time and using a min-heap to keep track of the end times of current passengers. As we process each trip, we remove all trips from the heap that have already ended, freeing up capacity. This allows us to always know the current number of passengers in the car and check if adding a new trip would exceed the capacity.

Approach

Sort Trips:
- Sort all trips by their start (pickup) location.
Use Min-Heap:
- Use a min-heap to keep track of ongoing trips, ordered by their end location.
Simulate the Process:
- For each trip:
  - Remove all trips from the heap whose end location is less than or equal to the current trip’s start location, adding their passengers back to the available capacity.
  - Subtract the current trip’s passengers from the available capacity.
  - If capacity goes negative, return false.
  - Add the current trip to the heap.
Return Result:
- If all trips are processed without exceeding capacity, return true.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class Solution {
public:
	bool carPooling(vector<vector<int>>& trips, int cap) {
		sort(trips.begin(), trips.end(), [](const auto& a, const auto& b) { return a[1] < b[1]; });
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
		for (auto& t : trips) {
			while (!pq.empty() && t[1] >= pq.top().first) {
				cap += pq.top().second;
				pq.pop();
			}
			cap -= t[0];
			if (cap < 0) return false;
			pq.push({t[2], t[0]});
		}
		return true;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


import "container/heap"
type Trip struct{ end, num int }
type MinHeap []Trip
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].end < h[j].end }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Trip)) }
func (h *MinHeap) Pop() interface{} { n := len(*h); x := (*h)[n-1]; *h = (*h)[:n-1]; return x }
func carPooling(trips [][]int, cap int) bool {
	sort.Slice(trips, func(i, j int) bool { return trips[i][1] < trips[j][1] })
	h := &MinHeap{}
	heap.Init(h)
	for _, t := range trips {
		for h.Len() > 0 && t[1] >= (*h)[0].end {
			cap += (*h)[0].num
			heap.Pop(h)
		}
		cap -= t[0]
		if cap < 0 { return false }
		heap.Push(h, Trip{t[2], t[0]})
	}
	return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
	public boolean carPooling(int[][] trips, int cap) {
		Arrays.sort(trips, Comparator.comparingInt(t -> t[1]));
		PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(t -> t[2]));
		for (int[] t : trips) {
			while (!pq.isEmpty() && t[1] >= pq.peek()[2]) {
				cap += pq.poll()[0];
			}
			cap -= t[0];
			if (cap < 0) return false;
			pq.offer(t);
		}
		return true;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
	fun carPooling(trips: Array<IntArray>, cap: Int): Boolean {
		trips.sortBy { it[1] }
		val pq = java.util.PriorityQueue<IntArray>(compareBy { it[2] })
		var c = cap
		for (t in trips) {
			while (pq.isNotEmpty() && t[1] >= pq.peek()[2]) {
				c += pq.poll()[0]
			}
			c -= t[0]
			if (c < 0) return false
			pq.add(t)
		}
		return true
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


import heapq
class Solution:
	def carPooling(self, trips: list[list[int]], cap: int) -> bool:
		trips.sort(key=lambda x: x[1])
		h = []
		for num, start, end in trips:
			while h and start >= h[0][0]:
				cap += heapq.heappop(h)[1]
			cap -= num
			if cap < 0:
				return False
			heapq.heappush(h, (end, num))
		return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
	pub fn car_pooling(mut trips: Vec<Vec<i32>>, cap: i32) -> bool {
		trips.sort_by_key(|t| t[1]);
		let mut h = BinaryHeap::new();
		let mut c = cap;
		for t in trips {
			while let Some(Reverse((end, num))) = h.peek() {
				if t[1] < *end { break; }
				c += num;
				h.pop();
			}
			c -= t[0];
			if c < 0 { return false; }
			h.push(Reverse((t[2], t[0])));
		}
		true
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


function carPooling(trips: number[][], cap: number): boolean {
	trips.sort((a, b) => a[1] - b[1]);
	const h: [number, number][] = [];
	for (const [num, start, end] of trips) {
		while (h.length && start >= h[0][0]) {
			cap += h.shift()![1];
		}
		cap -= num;
		if (cap < 0) return false;
		h.push([end, num]);
		h.sort((a, b) => a[0] - b[0]);
	}
	return true;
}

Complexity

⏰ Time complexity: O(n log n), where n is the number of trips. We sort the trips and use heap operations for each trip.
🧺 Space complexity: O(n), for the heap storing ongoing trips.

Car Pooling Problem#

Problem#

Examples#

Solution#

Method 1 – Prefix Sum (Difference Array)#

Intuition#

Approach#

Code#

Complexity#

Method 2 – Min-Heap for Ongoing Trips#

Intuition#

Approach#

Code#

Complexity#

Car Pooling Problem

Problem

Examples

Solution

Method 1 – Prefix Sum (Difference Array)

Intuition

Approach

Code

Complexity

Method 2 – Min-Heap for Ongoing Trips

Intuition

Approach

Code

Complexity