You are given an array people where people[i] is the weight of the ith 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.
Example 1:
Input: people = [1,2], limit = 3 Output: 1 Explanation: 1 boat (1, 2)
Example 2:
Input: people = [3,2,2,1], limit = 3 Output: 3 Explanation: 3 boats (1, 2), (2) and (3)
Example 3:
Input: people = [3,5,3,4], limit = 5 Output: 4 Explanation: 4 boats (3), (3), (4), (5)
Constraints:
1 <= people.length <= 5 * 1041 <= people[i] <= limit <= 3 * 104This approach utilizes sorting and a two-pointer technique. By sorting the array, we simplify the pairing process, always trying to pair the lightest and heaviest person possible to fit within the limit. This method is greedy because it always tries to use the lightest and heaviest pair that fits to use fewer boats.
Here, we first sort the array of people's weights. Then, using two pointers (one at the start and one at the end), we check if the lightest person (start) and the heaviest person (end) can share a boat. If they can, we move both pointers inward. If not, we move only the end pointer. We increment the boat count in each iteration. This ensures each person is considered.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since we're sorting in place.
In this approach, we again sort the weights, but the main focus is on maximizing each boat's capacity. If the heaviest person cannot be paired with the lightest one, they solely occupy a boat.
The approach involves sorting and using a two-pointer technique. Comparing outer values ensures efficient pairing unless the limit constraint prohibits including the lighter weight, causing the heavy weight to proceed alone.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) - Primary time usage is the sorting step. Space Complexity: O(1) when sorting in-place.
| Approach | Complexity |
|---|---|
| Two-pointer Approach | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since we're sorting in place. |
| Greedy Pairing | Time Complexity: O(n log n) - Primary time usage is the sorting step. Space Complexity: O(1) when sorting in-place. |
Boats to Save People - Leetcode 881 - Python • NeetCode • 28,023 views views
Watch 9 more video solutions →Practice Boats to Save People with our built-in code editor and test cases.
Practice on FleetCode