Problem 33.8 · Greedy AlgorithmsMedium

Boats to Save People

PatternGreedy Choice Two Pointers: Opposite Ends

What it teaches: Pair the heaviest person with the lightest if they fit; otherwise the heaviest goes alone.

Practise it on judges as “Boats to Save People”.

The problem

Each boat carries at most two people with total weight ≤ limit. Return the minimum number of boats.

Example 1

Input: people = [3,2,2,1], limit = 3
Output: 3

Constraints

1 ≤ n ≤ 5 × 10⁴
people[i] ≤ limit

Pattern clues in the wording

→ Pairs under a limit, minimise groups

These clues point to Greedy Choice: Make the best-looking choice at each step and never undo it, after proving that this choice is always safe.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	people = [1,2] limit = 3	1
2	people = [3,2,2,1] limit = 3	3
3	people = [3,5,3,4] limit = 5	4

From slow to fast

Approaches

1. Sort + two pointers · O(n log n)

Sort + two pointers

Time O(n log n) Space O(1) extra

l at the lightest, r at the heaviest. If they fit, l++. Always r−− and count a boat.

Approach 1

import java.util.Arrays;

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

Verdict: Exchange argument on the heaviest person.

Before you submit

Edge cases and common mistakes

Test these inputs

Everyone at the limit (n boats)
One person

Mistakes people make

Pairing the two lightest (wastes light partners the heavy ones need).

Interview

Follow-up questions

What if a boat could carry any number of people?

Command Palette

The problem

Approaches

Sort + two pointers

Edge cases and common mistakes

Follow-up questions