Problem overview
The function minBoats receives a slice weights with the weight of each student, an integer maxWeight, and an integer maxDiff. There are unlimited boats. Each boat carries one or two students. When it carries two, their combined weight must be at most maxWeight, and the absolute difference of their weights must be at most maxDiff. The function returns the smallest number of boats that can carry everybody.
In the first example, weights = []int{2, 4, 2, 1}, maxWeight = 6 and maxDiff = 1. The students of weight 1 and 2 can share a boat (sum 3, difference 1). The 4 can't pair with a 2, because the difference is 2. So the boats are (1, 2), (2) and (4), and the answer is 3.
In the second example, weights = []int{81, 37, 32, 88, 55, 93, 45, 72}, maxWeight = 100 and maxDiff = 10. Only (37, 32) and (55, 45) can pair up, so six boats are needed.
Approach: sort, then pair each student with the closest eligible partner
Every pair saves one boat, so the goal is to form as many valid pairs as possible. Sorting makes the choice easy to organise.
After sorting in ascending order, process the students from the heaviest to the lightest, with an index i. When it is the turn of student i and nobody has taken him yet, he rides either alone or with a lighter student. A lighter student p is an eligible partner when two conditions hold:
weights[p] + weights[i] <= maxWeight: the boat's weight limit;weights[i] - weights[p] <= maxDiff: the difference limit, which needs no absolute value becausepis the lighter one.
The weight limit has a nice property: the lighter the student, the easier it is to satisfy. Because the loop goes from heavy to light, i only gets lighter, so a student who fits with the current i by weight keeps fitting for every later i. A pointer p starting at the lightest student therefore only needs to move right. Every student it passes joins a stack of weight-eligible candidates.
The students are pushed in ascending order, so the heaviest candidate is always on top of the stack. That is the one closest in weight to i, which means that if even the top breaks the difference limit, every other candidate breaks it too. If the top fits, the two share a boat. A candidate on the stack may already have a boat, or may be i itself, and those entries are simply discarded when they reach the top. A small map, isTaken, records the students who are already paired.
Each student is pushed once and popped at most once, so after the sort the work is linear. Sorting costs O(n log n).
On the first example, the sorted weights are 1, 2, 2, 4:
- Student 4 (index 3): the candidates with weight sum at most 6 are 1, 2 and 2, so all three go onto the stack. The top is 2, and the difference 4 - 2 = 2 is more than 1, so the 4 rides alone. Boats: 1.
- Student 2 (index 2): this student is on top of the stack, so the entry is discarded. The next entry is the other 2, with difference 0, so they pair up. Boats: 2.
- Student 2 (index 1) is already taken and is skipped.
- Student 1 (index 0): the only entry left is the student himself, which is discarded, and the stack is empty. He rides alone. Boats: 3.
Step by step
- Sort the slice in ascending order with
sort.Ints. - Declare
answer, the number of boats, andp, the pointer to the next light student to push. Both start at 0. - Create the map
isTaken, amap[int]boolmarking students who already have a partner. - Create the stack as a
[][2]intslice of (weight, index) pairs. A plain stack is enough where one might expect a max heap, because the weights are pushed in ascending order, so the last one pushed is the heaviest. - Loop over
ifromlen(weights) - 1down to 0, heaviest first. - Push eligible students with a condition-only
for: whilep < iandweights[p] + weights[i] <= maxWeight. The conditionp < ikeeps the pointer from reaching the current student. - Do the push by appending
[2]int{weights[p], p}tostack, then incrementp. - Skip taken students. If
isTaken[i]is true,continue: that student already has a boat that was counted when his partner was processed. - Look for a partner with a loop that runs while the stack is not empty and the top's weight is within
maxDiffofweights[i]. - Discard unusable tops. Read the top pair into
top. If it isiitself or a taken student, pop it andcontinue. - Pair up. Otherwise mark both
iandtop[1]inisTaken. - Pop the partner and
break. - Count the boat. After the search, increment
answer. A student alone and a pair each cost one boat, and the pair is counted at its heavier member. - Return
answerafter the main loop.
The solution in Go
func minBoats(weights []int, maxWeight int, maxDiff int) int {
sort.Ints(weights)
answer, p := 0, 0
isTaken := make(map[int]bool)
stack := make([][2]int, 0)
for i := len(weights) - 1; i >= 0; i-- {
for p < i && weights[p]+weights[i] <= maxWeight {
stack = append(stack, [2]int{weights[p], p})
p++
}
if isTaken[i] {
continue
}
for len(stack) > 0 && weights[i]-stack[len(stack)-1][0] <= maxDiff {
top := stack[len(stack)-1]
if top[1] == i || isTaken[top[1]] {
stack = stack[:len(stack)-1]
continue
}
isTaken[i] = true
isTaken[top[1]] = true
stack = stack[:len(stack)-1]
break
}
answer++
}
return answer
}
The Go details worth knowing:
- Sorting in place.
sort.Ints(weights)reorders the caller's slice, and the function needsimport "sort". Copy the slice first if the original order matters. - Arrays as values.
[2]intis an array of exactly two ints, a value type that is copied on assignment.top := stack[len(stack)-1]copies the pair, and[2]int{weights[p], p}is an array literal. The pair holds the weight at index 0 and the original sorted position at index 1. - The slice as a stack. Push is
append, peek isstack[len(stack)-1], and pop isstack[:len(stack)-1], which shortens the slice without copying. The old slot stays in the backing array until an append overwrites it. - Missing map keys read as
false.isTaken[i]on a student who was never marked givesfalse, so no existence check is needed for amap[int]boolflag. - Short-circuit conditions. In
len(stack) > 0 && weights[i]-stack[len(stack)-1][0] <= maxDiff, the length test comes first, so the stack is never indexed when empty. - Two loop exits.
continueinside the inner loop restarts the inner loop on the new top, whilebreakleaves it. Neither affects the outer loop.
Complexity
Let n be the number of students.
Time: O(n log n). Sorting takes O(n log n). After that, p moves right only, so the push loop does at most n pushes in total. Each iteration of the search loop either pops one entry or ends the loop with a break or a failed difference test, so the pops add up to at most n plus one extra check per student. The main loop is linear.
Space: O(n). The stack and the isTaken map can each hold up to n entries.
Edge cases and common mistakes
- No students. An empty slice returns 0, since the main loop never runs.
- One student.
weights = []int{5}returns 1. - Equal weights.
weights = []int{3, 3}withmaxWeight = 6andmaxDiff = 0returns 1. WithmaxWeight = 5the weight limit blocks the pair and the result is 2. - Both limits matter. In the second example the sorted weights are 32, 37, 45, 55, 72, 81, 88, 93. For 93, 88, 81 and 72, even the lightest student (32) is too heavy to share by weight, so those four ride alone. For 55, the candidates 32, 37 and 45 fit by weight, and the top, 45, is within 10, so they pair. For 37, the student himself is discarded from the stack, and 32 is within 10, so they pair. That is 4 + 1 + 1 = 6 boats.
- Counting the boat for a taken student. A student already paired must be skipped, or the pair would be counted as two boats.
- Pairing a student with himself. A student can end up on the stack through an earlier, heavier
i. The checktop[1] == iprevents pairing him with himself. - Moving
pback. Resettingpfor eachiwould push students more than once and make the solution quadratic.
Testing
weights = []int{2, 4, 2, 1},maxWeight = 6,maxDiff = 1gives 3.weights = []int{81, 37, 32, 88, 55, 93, 45, 72},maxWeight = 100,maxDiff = 10gives 6.weights = []int{3, 3},maxWeight = 6,maxDiff = 0gives 1.weights = []int{3, 3},maxWeight = 5,maxDiff = 0gives 2.weights = []int{},maxWeight = 100,maxDiff = 10gives 0.