Problem Description
You are given an array people where people[i] is the weight of the i-th person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit. Return the minimum number of boats to carry every given person.
Key Insights
- We can utilize a two-pointer approach to efficiently pair the heaviest and lightest individuals.
- Sorting the people by weight allows us to easily find the optimal pairs for each boat.
- If the sum of the weights of the two individuals is within the limit, they can share a boat; otherwise, the heavier individual needs a separate boat.
Space and Time Complexity
Time Complexity: O(n log n) - due to sorting the array of weights.
Space Complexity: O(1) - we use a constant amount of space for pointers and counters.
Solution
The solution uses a two-pointer technique after sorting the array of people's weights. We initialize one pointer at the start (lightest person) and one at the end (heaviest person) of the sorted array. We check if the sum of the weights at these two pointers is less than or equal to the limit. If it is, both individuals can share a boat, and we move both pointers inward. If not, the heavier individual takes a separate boat, and only the end pointer is decremented. This process continues until all individuals are accounted for.