Minimize the number of boats needed to rescue everyone when each boat can carry at most two people and has a weight limit.
You are given an array of people weights and a boat weight limit. Each boat can carry at most two people at a time, and the total weight on a boat cannot exceed the limit.
Return the minimum number of boats required to carry everyone to safety.
A person can be placed alone or paired with at most one other person, as long as the boat's weight limit is not exceeded.
Input Format
- An integer array
people, wherepeople[i]is the weight of the -th person. - An integer
limit, the maximum total weight a boat can carry.
Output Format
- Return an integer representing the minimum number of boats needed.
Constraints
- Each boat carries at most 2 people.
Example 1
Input
people = [1,2], limit = 3
Output
1
Explanation
Both people can share one boat because their total weight is 3, which is within the limit.
Example 2
Input
people = [3,2,2,1], limit = 3
Output
3
Explanation
One optimal arrangement is [1,2], [2], and [3], using 3 boats.
Show 1 more example
Example 3
Input
people = [3,5,3,4], limit = 5
Output
4
Explanation
No two people can share a boat without exceeding the limit, so each person needs their own boat.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.