Question:
If a canoe can hold 2 kids and a maximum weight of 150 pounds, write a function that returns the minimum number of canoes needed
Time: O(n log n) due to sorting at the beginning.
public class Canoe {
final static int MAX_WEIGHT = 150;
public static void main(String[] args) {
// Use sorting algorithm O(n log n)
int[] weightList = {45, 67, 84, 100, 120, 134, 150, 167, 180, 200, 213};
System.out.println(numBoatsNeeded(weightList));
}
public static int numBoatsNeeded(int[] weightList) {
int numBoats = 0;
int i = 0;
int j = weightList.length-1;
while (i <= j) {
// When only one child remains
if (i == j) {
if (weightList[i] <= MAX_WEIGHT) {
numBoats++;
}
break;
}
/**
* Check sum of both ends, and if sum is less than max weight,
* place both on same boat.
*/
if (weightList[i] + weightList[j] <= MAX_WEIGHT) {
// Handled both lighter/heavier kid, so decrement
i++;
j--;
numBoats++;
// Check if heavier rider must fit in his own boat.
} else {
if (weightList[j] <= MAX_WEIGHT) {
numBoats++;
}
// Handled heavier kid
j--;
}
}
return numBoats;
}
}
Came up with a better solution or have a question? Comment below!