Shuttle Seating: Assign Passengers to Shuttle Seats Under Capacity Constraints

Question

## Problem

A company runs shuttle buses between offices. Each shuttle has a fixed number of seats. You are given a list of passenger requests, each specifying a pickup stop, a dropoff stop, and a priority level. Assign passengers to shuttles such that at no point does the number of passengers on board exceed capacity. Maximize total passengers served, breaking ties by priority.

```python
def assign_shuttle(requests: list[dict], capacity: int) -> list[int]:
    # requests[i] = {"id": int, "pickup": int, "dropoff": int, "priority": int}
    # stops are integers on a line; return list of assigned request ids
    pass
```

**Example:**
```
capacity = 2
requests = [
  {"id": 1, "pickup": 0, "dropoff": 3, "priority": 2},
  {"id": 2, "pickup": 1, "dropoff": 4, "priority": 1},
  {"id": 3, "pickup": 3, "dropoff": 5, "priority": 3}
]
Output: [1, 3]  # id=2 excluded; at stop 1-3 ids 1 and 2 would exceed capacity
```

## Follow-ups

1. How do you efficiently track current occupancy as the shuttle moves through stops?
2. If the shuttle can make multiple trips, how does the problem change?
3. What if passengers can be bumped by higher-priority late arrivals?
4. How would you handle concurrent shuttle assignments across a fleet?

Shuttle Seating: Assign Passengers to Shuttle Seats Under Capacity Constraints

Question Details

Full Details

Topics

More from Uber