LESSON 320 OF 414 · HEAP

Minimum Number of Boats in Rust: Greedy Pairing with Sorting and a Heap

Practice O(n log n) Read the full explanation

You are given an array weights where weights[i] is the weight of the i^th student, and an infinite number of boats where each boat can carry a maximum weight of maxWeight. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most maxWeight and the absolute difference of their weights shouldn't exceed maxDiff.

Return the minimum number of boats to carry every given student.

Example 1:

Input: weights = [2, 4, 2, 1], maxWeight = 6, maxDiff = 1
Output: 3
Explanation: 3 boats: (1, 2), (2) and (4)

Example 2:

Input: weights = [81, 37, 32, 88, 55, 93, 45, 72],
    maxWeight = 100, maxDiff = 10
Output: 6
Explanation: 6 boats (81), (37, 32), (88), (55, 45), (93), (72)

STEP 1 OF 21

Guided

Ctrl + Enter to check

RUST · HEAP

Minimum Number Of Boats in Rust, explained

Problem overview

The function min_boats receives the students' weights, weights, and two limits, max_weight and max_diff. A boat carries one student or two. Two students can share a boat only if their weights add up to at most max_weight and their weights differ by at most max_diff. There are as many boats as needed, and the function returns the fewest boats that carry everybody.

In the first example, weights = [2, 4, 2, 1], max_weight = 6 and max_diff = 1. The pairs that satisfy both rules are 1 with 2, and 2 with 2. The 4 is too far from every other weight. One best plan is the boats (1, 2), (2) and (4), which makes 3 boats.

In the second example, with limits 100 and 10, the answer is 6: the pairs (37, 32) and (55, 45) share boats, and the other four students ride alone.

Approach: sort, then pair the heaviest first

Every pair that shares a boat saves one boat, so the goal is to form as many valid pairs as possible. The heaviest student is the hardest to place, because the weight limit is tightest for them. A greedy strategy handles the students from heaviest to lightest and gives each one the best partner still available.

Sort the weights first, in ascending order. Then, for the student at position i, the possible partners are the students at lower positions:

The weight rule, weights[p] + weights[i] <= max_weight, is easier to meet the lighter the partner is. In a sorted vector, the partners that pass it are a prefix: positions from 0 up to some point.
The difference rule, weights[i] - weights[p] <= max_diff, is easier to meet the heavier the partner is.

So the best partner is the heaviest one that still passes the weight rule: if even that one is too far in weight, every other candidate is too. And choosing the heaviest valid one keeps the lighter students free for the lighter students that come later.

The lesson implements this with:

an index p that moves up the sorted vector and pushes every student who passes the weight rule with the current i into a max-heap, keyed by weight. As i only gets lighter, students that fit once keep fitting, so p never goes back and each student is pushed once;
a set, is_taken, with the students who already share a boat.

The heap may also contain stale entries: students who were paired since being pushed. They are discarded when they reach the top.

For the first example, the sorted weights are [1, 2, 2, 4]. The student of weight 4 is handled first: the candidates are 1, 2 and 2, and the heaviest of them, 2, is too far (the difference is 2), so the 4 gets its own boat. Then the 2 at position 2 takes the other 2 as a partner, so the pair uses one boat. The 2 at position 1 is already taken. Finally the 1 has only itself left, so it rides alone. That is 3 boats.

Step by step

Sort the weights in place with sort_unstable. The parameter is declared mut weights, which allows it. Equal numbers have no identity, so the order of equal values doesn't matter.
Declare the counters. answer is an i32 like the return value, and p is a usize because it indexes the vector. Both start at 0.
Create the set is_taken for positions that already have a partner.
Create the heap. It is a max-heap of (weight, position) tuples. Tuples compare by the first field first, so the heaviest candidate is on top.
Count down from the heaviest. Store the length in n, set i = n, and loop while i > 0 with i -= 1 at the top, so i runs from n - 1 down to 0. A usize can't be negative, so the usual i >= 0 countdown would never end.
Collect the candidates. An inner while loop runs while p < i and weights[p] + weights[i] <= max_weight.
Push each candidate as (weights[p], p), then increase p.
Skip students who already have a boat. If is_taken contains i, continue.
Look for a partner in a loop that peeks at the top of the heap, and ends with break if the heap is empty.
Read the top. The Some(&(top_w, top_idx)) arm copies the weight and the position out of the borrowed top. The copy ends the borrow, so the arm can call heap.pop().
Check the difference. If weights[i] - top_w > max_diff, break: this is the heaviest waiting candidate, so every other one is even further away.
Remove the top and check that it is still usable. After heap.pop(), if top_idx == i or the position is in is_taken, continue with the next top.
Pair them. Insert both i and top_idx into is_taken and break.
Count the boat by incrementing answer after the inner loop. This runs whether i found a partner or rides alone. A student who was already taken was skipped before this point, so the pair is counted once, at the heavier student.
Return answer as the final expression, with no semicolon.

The solution in Rust

impl Solution {
    fn min_boats(mut weights: Vec<i32>, max_weight: i32, max_diff: i32) -> i32 {
        weights.sort_unstable();
        let mut answer = 0i32;
        let mut p = 0usize;
        let mut is_taken = std::collections::HashSet::new();
        let mut heap = std::collections::BinaryHeap::new();

        let n = weights.len();
        let mut i = n;
        while i > 0 {
            i -= 1;
            while p < i && weights[p] + weights[i] <= max_weight {
                heap.push((weights[p], p));
                p += 1;
            }
            if is_taken.contains(&i) {
                continue;
            }
            loop {
                match heap.peek() {
                    None => break,
                    Some(&(top_w, top_idx)) => {
                        if weights[i] - top_w > max_diff {
                            break;
                        }
                        heap.pop();
                        if top_idx == i || is_taken.contains(&top_idx) {
                            continue;
                        }
                        is_taken.insert(i);
                        is_taken.insert(top_idx);
                        break;
                    }
                }
            }
            answer += 1;
        }
        answer
    }
}

The Rust details worth a closer look:

Inferred collection types. The set and the heap are created without type annotations. The compiler works out their element types from later use: is_taken from contains(&i) and insert(i) with a usize, and heap from the pushed (i32, usize) tuples. The full paths, std::collections::HashSet, work without any use line.
Counting down with usize. Decrementing at the top of the loop with i -= 1 makes the loop body see n - 1 down to 0, and the condition i > 0 stops it before an underflow. In a debug build, subtracting 1 from a usize that holds 0 panics. In an optimized build it wraps to a huge number.
Matching on peek(). peek() returns an Option holding a reference to the top. The pattern Some(&(top_w, top_idx)) destructures both the reference and the tuple, and copies the two numbers. Without the copy, the heap would stay borrowed, and heap.pop() inside the arm would not compile.
continue and break inside match. They apply to the nearest enclosing loop, the inner loop, and not to the match. The continue inside the inner loop goes back to heap.peek().
Why (weight, position) tuples. The weight alone would lose track of which student it was. Tuples also order by the first field, so the heaviest weight is on top, and ties are broken by the larger position.
Overflow. weights[p] + weights[i] is an i32 sum. In an optimized build, two very large weights would wrap silently. The lesson's tests keep the weights small.

Complexity

Time: O(n log n). Sorting takes O(n log n). After that, each student is pushed onto the heap at most once, because p only moves forward, and popped at most once. Each heap operation is O(log n), and the set operations are O(1) on average.

Space: O(n). The heap and the set each hold at most one entry per student.

Edge cases and common mistakes

No students. The loop doesn't run, and the answer is 0.
One student. [5] returns 1.
Fits by weight but not by difference. [3, 4] with max_weight = 7 and max_diff = 0 returns 2. The sum is fine, but the weights differ by 1.
Fits by difference but not by weight. [3, 3] with max_weight = 5 would need 2 boats. The sum 6 is too much.
Equal weights. [5, 5, 5] with max_weight = 10 and max_diff = 0 returns 2: one pair, and one student alone. The odd student out still counts.
Pairing a student with themselves. The condition p < i and the check top_idx == i both prevent it.
Counting a pair twice. Both students of a pair go into is_taken, and the lighter one is skipped when its turn comes. Without that, the lighter student would get an extra boat.
Looking only at the weight limit. Pairing the lightest with the heaviest, as in the classic version of this puzzle, ignores max_diff and gives wrong answers here.

Testing

weights = [2, 4, 2, 1], max_weight = 6, max_diff = 1 gives 3.
weights = [81, 37, 32, 88, 55, 93, 45, 72], max_weight = 100, max_diff = 10 gives 6.
weights = [5, 5, 5], max_weight = 10, max_diff = 0 gives 2.
weights = [1, 2, 3, 4], max_weight = 5, max_diff = 3 gives 2.
weights = [3, 3], max_weight = 6, max_diff = 0 gives 1.
weights = [], max_weight = 10, max_diff = 5 gives 0.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free