Boats to Save People
Minimum boats to ferry people with weight limit — sort, pair heaviest with lightest if they fit.
2 min read
greedy two-pointers sorting
Problem#
Each boat takes at most 2 people with total weight ≤ limit. Return minimum boats to ferry everyone.
Examples#
people = [1,2], limit = 3→1people = [3,2,2,1], limit = 3→3
Constraints#
1 <= n <= 5 * 10^4.
Approach#
Sort. Two pointers l (lightest) and r (heaviest). If they fit together, take both; else send heaviest alone. Count boats.
Solution#
class Solution {public: int numRescueBoats(vector<int>& people, int limit) { sort(people.begin(), people.end()); int l = 0, r = people.size() - 1, boats = 0; while (l <= r) { if (people[l] + people[r] <= limit) ++l; --r; ++boats; } return boats; }};func numRescueBoats(people []int, limit int) int { sort.Ints(people) l, r, boats := 0, len(people)-1, 0 for l <= r { if people[l]+people[r] <= limit { l++ } r-- boats++ } return boats}from typing import List
class Solution: def numRescueBoats(self, people: List[int], limit: int) -> int: people.sort() l, r, boats = 0, len(people) - 1, 0 while l <= r: if people[l] + people[r] <= limit: l += 1 r -= 1 boats += 1 return boatsvar numRescueBoats = function(people, limit) { people.sort((a, b) => a - b); let l = 0, r = people.length - 1, boats = 0; while (l <= r) { if (people[l] + people[r] <= limit) l++; r--; boats++; } return boats;};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; }}function numRescueBoats(people: number[], limit: number): number { people.sort((a, b) => a - b); let l = 0, r = people.length - 1, boats = 0; while (l <= r) { if (people[l] + people[r] <= limit) l++; r--; boats++; } return boats;}Editorial#
The heaviest person always takes one boat. The greedy decision is whether to also send the lightest with them. If they fit, pair them — never worse than wasting a half-boat on the heaviest alone. If not, the lightest will pair with someone else later, but the heaviest’s boat is fixed.
Complexity#
- Time: O(n log n).
- Space: O(1).
Concept revision#
Related#