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

Related Tags:

Algorithm Pseudocode

  1. Sort the array in ascending order. O(n log n)
  2. Start with indices on either ends i, and j.
  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!

Next Challenge: First 100 of Fibonacci