Boats to Save People

MEDIUM✓ CHIP-TIMEDLC #881 — FULL STATEMENT ↗

The drill: Ferry everyone across using boats that each carry at most two people under a fixed weight limit; find the fewest boats needed to move every person.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A group of people, each with their own weight, needs ferrying across using boats that hold at most two people and never exceed a fixed weight limit per trip.

Every boat that leaves counts against the total, whether it carries one person or two, and every person must eventually be moved — nobody is left behind.

The goal is the fewest boats that get everyone across, not the assignment of who rides with whom.

EX 01

people = [1, 2] · limit = 3

→ 1

MINIMUM SIZE, BOTH FIT ONE BOAT

EX 02

people = [3, 2, 2, 1] · limit = 3

→ 3

ONLY THE TWO LIGHTEST CAN SHARE

EX 03

people = [3, 5, 3, 4] · limit = 5

→ 4

NOBODY CAN PAIR, EVERY BOAT RIDES ALONE

the group ranges from one person up to around fifty thousand
each individual weight never exceeds the boat's own limit alone
a boat carries at most two people and must stay within the limit
only the minimum boat count is reported

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Every boat should carry the heaviest person still waiting, since nobody else is harder to place. Who, if anyone, should ride along with them?

HINT 2 THE STRUCTURE

Sort by weight. The heaviest person left is the hardest to pair; check whether the lightest person left can share a boat with them.

HINT 3 ONE STEP FROM THE ANSWER

Two pointers from both ends of the sorted array: the heaviest always boards. The lightest joins them only if the pair still fits the limit — otherwise the lightest waits for a future boat. Either way, the boat leaves and both pointers move one step closer.

COACH'S BOARD — THE PATTERN, STEP BY STEP

HEAVIEST PLUS LIGHTESTPATTERN · TWO POINTERS FROM BOTH ENDSpeople = [1, 2, 3, 4, 5] (sorted) · limit = 6

BOATS LAUNCHED

— empty —

STEP 1

Limit 6. Heaviest and lightest pair up from sorted ends: L=0 (1kg), R=4 (5kg).

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/boats-to-save-people.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people = sorted(people)
        l, r = 0, len(people) - 1
        boats = 0
        while l <= r:
            if people[l] + people[r] <= limit:
                l += 1
            r -= 1
            boats += 1
        return boats

TIME O(N LOG N)SPACE O(1)PYTHON · RACE PACE · 11 LN

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        remaining = list(people)
        boats = 0
        while remaining:
            heaviest_idx = max(range(len(remaining)), key=lambda idx: remaining[idx])
            heaviest = remaining.pop(heaviest_idx)
            boats += 1

            partner_idx = None
            best = None
            for idx, w in enumerate(remaining):
                if heaviest + w <= limit and (best is None or w < best):
                    best = w
                    partner_idx = idx
            if partner_idx is not None:
                remaining.pop(partner_idx)
        return boats

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 18 LN

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int l = 0;
        int r = people.length - 1;
        int boats = 0;
        while (l <= r) {
            if (people[l] + people[r] <= limit) {
                l++;
            }
            r--;
            boats++;
        }
        return boats;
    }
}

TIME O(N LOG N)SPACE O(1)JAVA · RACE PACE · 16 LN

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        List<Integer> remaining = new ArrayList<>();
        for (int p : people) {
            remaining.add(p);
        }
        int boats = 0;
        while (!remaining.isEmpty()) {
            int heaviestIdx = 0;
            for (int i = 1; i < remaining.size(); i++) {
                if (remaining.get(i) > remaining.get(heaviestIdx)) {
                    heaviestIdx = i;
                }
            }
            int heaviest = remaining.remove(heaviestIdx);
            boats++;

            int partnerIdx = -1;
            Integer best = null;
            for (int i = 0; i < remaining.size(); i++) {
                int w = remaining.get(i);
                if (heaviest + w <= limit && (best == null || w < best)) {
                    best = w;
                    partnerIdx = i;
                }
            }
            if (partnerIdx != -1) {
                remaining.remove(partnerIdx);
            }
        }
        return boats;
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 33 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED