You are given an array weights where weights[i] is the weight of the ith student, and an infinite number of boats where each boat can carry a maximum weight of maxWeight. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most maxWeight and the absolute difference of their weights shouldn't exceed maxDiff.
Return the minimum number of boats to carry every given student.
Example 1:
Input: weights = [2, 4, 2, 1], maxWeight = 6, maxDiff = 1 Output: 3 Explanation: 3 boats: (1, 2), (2) and (4)
Example 2:
Input: weights = [81, 37, 32, 88, 55, 93, 45, 72],
maxWeight = 100, maxDiff = 10
Output: 6
Explanation: 6 boats (81), (37, 32), (88), (55, 45), (93), (72)
Walkthroughs of the solution. Try the steps first, then watch to compare approaches.
Solution #1 · O(n log n)
Free plan: 30 tutor messages. Premium is unlimited.