Skip to content
Katabench
Try free

Boats to Save People

Medium About 20 min Free, no account needed

Pair people into two-person boats under a weight limit, using as few boats as possible.

The brief

Given an array people of weights and an integer limit, return the minimum number of boats to carry everyone, where each boat carries at most two people whose combined weight is at most limit.

  • Every individual weight is at most limit.

The performance bar

The obvious approach pairs the heaviest person by scanning a shrinking list for the best partner; every scan and removal shifts the list, O(n2) overall. The hidden test loads 200,000 people, so you need an approach closer to O(n log n) that does not rescan a shrinking list for each boat.

Starter code

C#
using System;

public class Solution
{
    // TODO: return the minimum number of two-person boats under the weight limit.
    public int NumRescueBoats(int[] people, int limit)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Greedy algorithms
Make the locally best choice when an exchange argument proves it stays globally optimal.
Two pointers
Walk a sorted or symmetric sequence from both ends, or fast and slow, instead of checking every pair.

Related katas