Get Across River: Find Minimum Time for a Group to Cross a River Using a Boat with Limited Capacity

Question

## Problem

A group of people must cross a river using a single boat that holds at most 2 people. Each person has a crossing time; when 2 cross together, they move at the slower person's speed. The boat must be rowed back by someone. Find the minimum total time for all `n` people to cross.

```python
def min_crossing_time(times: list[int]) -> int:
    pass
```

**Example:**
```
times  = [1, 2, 5, 10]  # sorted
Strategy A: 1+2 cross (2), 1 returns (1), 5+10 cross (10), 2 returns (2), 1+2 cross (2) -> 17
Strategy B: 1+10 cross (10), 1 back (1), 1+5 cross (5), 1 back (1), 1+2 cross (2) -> 19
output -> 17
```

## Approach

For 4+ people: at each step, compare two strategies -- use the fastest person as a shuttle vs. pair the two slowest. Take the minimum. O(n log n) after sorting.

## Follow-ups
1. Prove that the greedy strategy is optimal -- or construct a counterexample for groups larger than 4.
2. The boat capacity is `k` (not just 2). How does the strategy generalize?
3. There are 2 boats available. How does parallel crossings change the optimal strategy?
4. Some people refuse to cross with certain others (conflict list). How do you handle pairing constraints?

Get Across River: Find Minimum Time for a Group to Cross a River Using a Boat with Limited Capacity

Question Details

Full Details

Topics

More from Square/Block