# Number of canoes needed

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

## Algorithm Pseudocode

1. Sort the array in ascending order. O(n log n)
3. Compare the sum of values at i and j to 150. If less than or equal, decrement both indices and increment numBoats.
4. If greater, check if heavier boy qualifies (is <= 150 lbs). If so, increment numBoats. If not, do nothing. In either case decrement j.

## Complexity

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!