#1094 Car Pooling
the problem
In plain words
A car drives east only and has capacity seats. trips[i] = [numPassengers, from, to]: those passengers get in at km from and out at km to. Can every trip be served? (This is the free cousin of Meeting Rooms II.)
in trips = [[2,1,5],[3,3,7]], capacity = 4
out false
Between km 3 and 5 there are 5 passengers.
in trips = [[2,1,5],[3,3,7]], capacity = 5
out true
- 1 ≤ trips.length ≤ 1000
- 1 ≤ numPassengers ≤ 100
- 0 ≤ from < to ≤ 1000
- 1 ≤ capacity ≤ 10⁵
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternSweep line & difference array
Only the points where people get in or out matter. Add at from, subtract at to, and sweep with a running total.
solutions
From brute force to optimal
For each km, add up the passengers of every trip covering it.
- For km in 0..1000, sum trips with from ≤ km < to.
- Fail if any sum exceeds capacity.
L = 1001 road points × n trips.
One counter.
class Solution { public boolean carPooling(int[][] trips, int capacity) { for (int km = 0; km <= 1000; km++) { // check every point on the road int inCar = 0; for (int[] t : trips) { if (t[1] <= km && km < t[2]) inCar += t[0]; // on board between from and to } if (inCar > capacity) return false; } return true; }}change[from] += p, change[to] −= p. A running sum gives the passengers on board at every km.
- Build the difference array.
- Sweep km 0..1000 with a running sum.
- Fail if it ever exceeds capacity.
Two writes per trip, then one pass over L = 1001 points.
The difference array.
class Solution { public boolean carPooling(int[][] trips, int capacity) { int[] change = new int[1001]; // difference array over the road for (int[] t : trips) { change[t[1]] += t[0]; // they get in at "from" change[t[2]] -= t[0]; // and out at "to" } int inCar = 0; for (int km = 0; km <= 1000; km++) { // sweep left to right inCar += change[km]; if (inCar > capacity) return false; } return true; }}Keep only the event points in a TreeMap. Iterating it in key order is the sweep.
- merge(from, +p), merge(to, −p).
- Walk values() in order with a running sum.
2n TreeMap updates at O(log n) each.
At most 2n keys.
class Solution { public boolean carPooling(int[][] trips, int capacity) { TreeMap<Integer, Integer> change = new TreeMap<>(); // only the points where something happens for (int[] t : trips) { change.merge(t[1], t[0], Integer::sum); change.merge(t[2], -t[0], Integer::sum); } int inCar = 0; for (int delta : change.values()) { // ascending location order inCar += delta; if (inCar > capacity) return false; } return true; }}in the room
How to say it in the interview
talk track
- Say "sweep line" and explain why
tois a drop-off before anyone at the same km boards. The −p and +p land in the same slot, so it works out.
traps
- Subtracting at
to + 1. Passengers leave atto, so the seat is free for someone boarding there.
what they ask next
Follow-ups
Locations up to 10⁹?
The int[] would be too big. Use the TreeMap of events (or sort the 2n events), O(n log n).
before you submit
Edge cases to test
- Drop-off and pick-up at the same km don't overlap: [2,1,5] and [3,5,7] fit in 3 seats.
- A single trip bigger than the capacity → false.
- Trips given out of order: the difference array doesn't care.
practise next
Similar problems
- #253Meeting Rooms IIMediumin IntervalsLeetCode Premium
- #303Range Sum Query - ImmutableEasyin Hashing