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

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)}$.

---

---

---