Layover: Minimum Connection Time to Catch Connecting Flights

Question

## Problem

You are given a list of flights: each flight has a `departure_airport`, `arrival_airport`, `arrival_time`, and a list of connecting flights from that airport. A layover is valid only if the connecting flight departs at least `min_layover` minutes after arrival.

Given a starting airport and a destination, find the minimum total travel time (including layovers) across all valid routes.

```python
def min_travel_time(
    flights: list[dict],
    start: str,
    destination: str,
    min_layover: int
) -> int:  # returns -1 if unreachable
    pass
```

**Example:**
```
flights = [
  {"id": "F1", "from": "JFK", "to": "ORD", "depart": 0,  "arrive": 150},
  {"id": "F2", "from": "ORD", "to": "LAX", "depart": 180, "arrive": 360},
  {"id": "F3", "from": "ORD", "to": "LAX", "depart": 160, "arrive": 400}
]
min_layover = 20
start = "JFK", destination = "LAX"

F1 arrives ORD at 150. F2 departs at 180 (layover=30 >= 20). Valid.
F3 departs at 160 (layover=10 < 20). Invalid.

Output: 360  (total elapsed from time 0)
```

## Follow-ups

1. Model this as a graph problem. Which shortest-path algorithm applies, and why?
2. What if you want to minimize the number of layovers rather than total time?
3. How do time zones affect your model?
4. How would you handle canceled or delayed flights in real time?

Layover: Minimum Connection Time to Catch Connecting Flights

Question Details

Full Details

Topics

More from Airbnb