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 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
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.
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
- Container With Most Water Medium Free Pick two lines that, with the x-axis, hold the most water.
- Find the Duplicate Number Medium Free Find the one repeated value in an array of n+1 numbers from 1..n, without allocating a set to do it.
- Integer to Roman Medium Free Write Roman numerals the way Romans did - greedily.
- Longest Palindromic Substring (Length) Medium Free How long is the longest palindrome hiding in the string?