Daily Coding Problem #291: Minimum Number of Boats to save population

Problem Definition

An imminent hurricane threatens the coastal town of Codeville. If at most two people can fit in a rescue boat, and the maximum weight limit for a given boat is k, determine how many boats will be needed to save everyone.

For example, given a population with weights [100, 200, 150, 80] and a boat limit of 200, the smallest number of boats required will be 3.

Solution

To be able to determine the smallest number of boats, we need to maximize the number of pairing. To maximize the number of pairing, for given weight we must pair with the maximum value possible. If we pair we smaller weight we may not get the minimum number.

For example, given a population with weights [30, 150, 170, 50] and a boat limit of 200. Here if we pair 30 with 50, then 150 and 170 are left alone hence resulting into the result 3. However, it is possible to pair 30 with 170 and 50 with 150 satisfying the constraint. This pairing will give the result 2.

Therefore, for each weight, we must pair it with the maximum weight possible. We might be tempted to use following solution:

1. For each weight, iterate through rest of the weights to find the maximum weight with which it can be paired. Make sure to avoid already used weight.

This solution will work, but it will have time complexity $O(n^2)$

Solution Using Sorting

Following is implementation is using sorting. This method is still $O(n^2)$. It takes $O(n)$ time find pair. I am trying to figure out if the pair could be found in $O(logn)$ time instead so that the overall time complexity will be $O(nlogn)$

Implementation

	/* File: Boats.java
	* Created: 7/24/2019
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2019 Hogwart Inc.
	*/
	import java.util.Arrays;
	import java.util.Collections;
	//=======================================================================================
	/**
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class Boats {
	/**
	* Driver method
	*/
	public static void main(String[] args) {
	System.out.println(compute(new Integer[]{100, 200, 150, 80}, 200) + " == " + 3);
	System.out.println(compute(new Integer[]{30, 40, 70, 100, 200, 150, 80}, 200) + " == " + 4);
	System.out.println(compute(new Integer[]{}, 1) + " == " + 0);
	System.out.println(compute(new Integer[]{100}, 200) + " == " + 1);
	System.out.println(compute(new Integer[]{200, 10, 200, 200}, 200) + " == " + 4);
	System.out.println(compute(new Integer[]{200, 200, 10, 200, 200}, 200) + " == " + 5);
	System.out.println(compute(new Integer[]{170, 160, 30, 90}, 200) + " == " + 3);
	System.out.println(compute(new Integer[]{150, 150, 150, 30}, 200) + " == " + 3);
	} // main
	//-----------------------------------------------------------------------------------------------
	/**
	* Computes number of boats required
	* @param weights array of weights of population
	* @param limit weight limit of each boat
	* @return number of boats needed
	*
	*/
	public static int compute(Integer[] weights, int limit) {
	if(weights.length == 0) return 0;
	Arrays.sort(weights, Collections.reverseOrder());
	boolean[] used = new boolean[weights.length];
	int boats = 0;
	for(int idx = 0; idx < weights.length; idx++) {
	if (used[idx]) continue;
	if (weights[idx] == limit) {
	boats++;
	continue;
	}
	int pair = findPair(weights, used, limit - weights[idx], idx+1, weights.length-1);
	if (pair > -1) {
	used[pair] = true;
	}
	boats++;
	}
	return boats;
	} // compute
	/**
	* Find pairing for the limit provided
	* @param weights
	* @param used
	* @param limit
	* @param lo
	* @param hi
	* @return
	*/
	private static int findPair(Integer[] weights, boolean[] used, int limit, int lo, int hi) {
	int lastValid = -1;
	for (int i = hi; i >= lo; i--) {
	if (!used[i]) {
	if (weights[i] == limit) {
	return i;
	} else if (weights[i] < limit) {
	lastValid = i;
	} else {
	return lastValid;
	}
	} else {
	continue;
	}
	}
	return lastValid;
	} // findPair
	} // Boats

view raw Boats.java hosted with ❤ by GitHub

Complexity

Sorting can be done in $O(n logn)$ time.
Finding a pair will take $O(n)$ time.

$\therefore$ The Time Complexity of this method will be $\cal{O(n^2)}$.

---

---

---