Problem overview
The method MinBoats receives the students' weights, the boat capacity maxWeight and a fairness limit maxDiff. A boat carries one student or two. Two students can share a boat only if their weights add up to at most maxWeight and differ by at most maxDiff. The method returns the smallest number of boats that carries everyone.
For weights = [2, 4, 2, 1], maxWeight = 6 and maxDiff = 1, three boats are enough. A pair of 1 and 2 goes together, one 2 goes alone, and 4 goes alone. The student of weight 4 can't be paired: the only partners that fit by total weight weigh 2 or less, and 4 and 2 differ by 2.
In the second example, [81, 37, 32, 88, 55, 93, 45, 72] with maxWeight = 100 and maxDiff = 10 needs six boats. Only 37 with 32 and 55 with 45 can share.
Approach: heaviest first, choose the best partner
Every pair that shares a boat saves one boat, so the goal is to form as many valid pairs as possible. The heaviest students are the hardest to pair, since they have the fewest partners that fit the total weight. So we process the students from the heaviest down.
For the current student i, a partner must be lighter (an earlier position in the sorted array) and satisfy two rules:
- The sum rule:
weights[p] + weights[i] <= maxWeight. In a sorted array, the students that satisfy this form a prefix, and the prefix grows asigets lighter. - The difference rule:
weights[i] - weights[p] <= maxDiff. Among the students who pass the sum rule, the heaviest one has the smallest difference, so it is the best candidate.
That suggests the structure: a pointer p that moves right and pushes each student who passes the sum rule into a max heap ordered by weight. The top of the heap is then the heaviest waiting candidate, which is the one the difference rule favours. If even the top is too far from i in weight, every other candidate is too, and i sails alone.
Because i only decreases, the condition weights[p] + weights[i] <= maxWeight only gets easier, so p never has to move back. Each student enters the heap at most once.
Some entries in the heap become unusable: an entry for the student who is currently i, or one who was already paired. The code removes such entries when they reach the top, instead of deleting them from the middle.
On the first example, the sorted weights are [1, 2, 2, 4]. The student of weight 4 pushes everyone else into the heap (each sum is at most 6), but the heaviest candidate has weight 2 and the difference is 2, so 4 takes a boat alone. The next student, weight 2, pairs with the other 2 (difference 0), and that one is marked as taken. The lightest student, weight 1, finds only its own entry in the heap, discards it and takes a boat alone. The total is three boats.
Step by step
- Sort
weightsin ascending order. - Declare
answerandp, both starting at 0.answercounts boats andpis the pointer that feeds candidates into the heap. - Create the
HashSetisTaken, which will hold the sorted positions of students who already share a boat. - Create the heap. Each element is an array
{weight, index}, and its priority is the weight. A comparer that reverses the normal order puts the heaviest on top. - Loop over positions from heaviest to lightest, with
igoing fromweights.Length - 1down to 0. - Feed the heap. While
p < iandweights[p] + weights[i] <= maxWeight, the student atpis a candidate. - Push the candidate as
new int[]{weights[p], p}with priorityweights[p], then incrementp. - Skip taken students. If
iis inisTaken, a heavier student has already paired with it and the boat is counted, socontinue. - Look for a partner while the heap is not empty and the top candidate is within
maxDiffofweights[i]. - Discard unusable tops. If the top is
iitself or is already taken, dequeue it and look at the next one. - Record the pairing. Otherwise add both
iand the top's index toisTaken. - Remove the partner and stop searching. Dequeue the top and
break. - Count the boat. After the inner loop, increment
answer. A pair and a lone student both take one boat. - Return
answerafter the main loop.
The solution in C#
class Solution {
public int MinBoats(int[] weights, int maxWeight, int maxDiff) {
Array.Sort(weights);
int answer = 0, p = 0;
HashSet<int> isTaken = new HashSet<int>();
PriorityQueue<int[], int> heap = new PriorityQueue<int[], int>(Comparer<int>.Create((x, y) => y - x));
for (int i = weights.Length - 1; i >= 0; i--) {
while (p < i && weights[p] + weights[i] <= maxWeight) {
heap.Enqueue(new int[]{weights[p], p}, weights[p]);
p++;
}
if (isTaken.Contains(i)) {
continue;
}
while (heap.Count > 0 && weights[i] - heap.Peek()[0] <= maxDiff) {
if (heap.Peek()[1] == i || isTaken.Contains(heap.Peek()[1])) {
heap.Dequeue();
continue;
}
isTaken.Add(i);
isTaken.Add(heap.Peek()[1]);
heap.Dequeue();
break;
}
answer++;
}
return answer;
}
}
Some C# details to notice:
Array.Sortsorts in place. It reorders the caller's array. That is acceptable here, but it is worth remembering when the original order matters.- Arrays as heap elements.
PriorityQueue<int[], int>stores anint[]element with anintpriority.Peek()returns the element, soheap.Peek()[0]is the weight andheap.Peek()[1]is the position. The priority itself isn't returned. - The comparer works on priorities.
Comparer<int>.Create((x, y) => y - x)compares theintpriorities, not the arrays, and reverses their order. For very large values the subtraction could overflow, andy.CompareTo(x)would be the safe form. HashSet<int>givesContainsandAddin constant time on average. Adding a value that is already present does nothing.continueandbreakapply to the nearest enclosing loop. Thecontinueinside the innerwhilemoves on to the next top of the heap, while thecontinuebefore it moves to the next student.
Complexity
Time: O(n log n). Sorting costs O(n log n). Each student is pushed once and popped at most once, each in O(log n), and p never moves backwards.
Space: O(n). The heap and the set can each hold up to n entries.
Edge cases and common mistakes
- One student or none. A single student needs one boat, and an empty array needs none.
- A pair that fits by weight but not by difference. With
[1, 5],maxWeight = 10andmaxDiff = 3, the pair weighs 6 in total but differs by 4, so two boats are needed. - A pair that is close but too heavy. With
[3, 3, 3, 3],maxWeight = 5, nothing can share, and four boats are needed. WithmaxWeight = 6andmaxDiff = 0, the four equal students form two pairs. - Counting a paired student twice. The partner is marked in
isTaken, so the loop skips it later without adding a boat. - Pairing a student with itself. The heap can hold the entry for
iitself, with difference 0. The checkheap.Peek()[1] == idiscards it. - Taking the lightest partner. A pair must be close in weight, so the heaviest candidate is the right choice. Taking the lightest would break the difference rule more often.
- Forgetting that sorting changes positions. The positions in
isTakenand in the heap refer to the sorted array, not the original one.
Testing
weights = [2, 4, 2, 1],maxWeight = 6,maxDiff = 1gives3.weights = [81, 37, 32, 88, 55, 93, 45, 72],maxWeight = 100,maxDiff = 10gives6.weights = [1, 5],maxWeight = 10,maxDiff = 3gives2.weights = [3, 3, 3, 3],maxWeight = 6,maxDiff = 0gives2.weights = []gives0.