Two Pointers Pointers from both ends
160. Boats to Save People
You are given an array people, where people[i] is the weight of the i-th person, and an integer limit.
Everyone has to be carried across a river by boat, and there are as many boats as you need.
A boat carries at most two people at a time, and the total weight of the people in it must be at most
limit. Return the fewest boats needed to carry everyone.
Every person weighs at most limit, so anyone can ride in a boat alone.
Example 1
Input: people = [7, 2, 5, 4, 8, 3], limit = 9
4Explanation: The person of weight 8 rides alone, because even 8 + 2 is over 9. The other five people need at least three boats, for example (7, 2), (5, 4) and (3).
Example 2
Input: people = [1, 1, 1, 1, 1], limit = 100
3Explanation: The boat could carry far more weight, but it holds at most two people. Two boats carry two people each, and the last person rides alone.
Example 3
Input: people = [9, 1, 10, 5, 5], limit = 10
3Explanation: The person of weight 10 rides alone. 9 and 1 weigh exactly 10 together, so they share a boat, and so do the two people of weight 5.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ people.length ≤ 1051 ≤ people[i] ≤ limit ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.