Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 291
Good morning! Here's your coding interview problem for today.

This problem was asked by Glassdoor.

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 three.

Pull request description:
Day291
Resolves #596.

Patch:
diff --git a/README.md b/README.md
index d8ba37f..e9aac2b 100644
--- a/README.md
+++ b/README.md
@@ -300,3 +300,4 @@ problems from
 * [Day 287](https://github.com/vaskoz/dailycodingproblem-go/issues/587)
 * [Day 288](https://github.com/vaskoz/dailycodingproblem-go/issues/590)
 * [Day 290](https://github.com/vaskoz/dailycodingproblem-go/issues/594)
+* [Day 291](https://github.com/vaskoz/dailycodingproblem-go/issues/596)
diff --git a/day291/problem.go b/day291/problem.go
new file mode 100644
index 0000000..3c2e83f
--- /dev/null
+++ b/day291/problem.go
@@ -0,0 +1,31 @@
+package day291
+
+import "sort"
+
+// BoatsNeededForEvacuation returns the minimum number of boats needed to
+// evacuate Codeville before the hurricane.
+// peopleWeights is a list of the people needing evacuation and k is the
+// max weight allowed on each boat.
+func BoatsNeededForEvacuation(peopleWeights []int, k int) int {
+	weights := make([]int, len(peopleWeights))
+	copy(weights, peopleWeights)
+	sort.Sort(sort.Reverse(sort.IntSlice(weights)))
+	var boats int
+	for i, weight := range weights {
+		if weight != -1 {
+			if weight > k {
+				panic("individual is over boat's weight. can't evacuate.")
+			}
+			remaining := k - weight
+			weights[i] = -1
+			for j := i + 1; j < len(weights); j++ {
+				if weights[j] != -1 && weights[j] <= remaining {
+					weights[j] = -1
+					break
+				}
+			}
+			boats++
+		}
+	}
+	return boats
+}


Test patch:
diff --git a/day291/problem_test.go b/day291/problem_test.go
new file mode 100644
index 0000000..e61777e
--- /dev/null
+++ b/day291/problem_test.go
@@ -0,0 +1,39 @@
+package day291
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	weights []int
+	k       int
+	boats   int
+}{
+	{[]int{100, 200, 150, 80}, 200, 3},
+}
+
+func TestBoatsNeededForEvacuation(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if boats := BoatsNeededForEvacuation(tc.weights, tc.k); boats != tc.boats {
+			t.Errorf("Expected %v, got %v", tc.boats, boats)
+		}
+	}
+}
+
+func TestBoatsNeededForEvacuationCant(t *testing.T) {
+	t.Parallel()
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("Expected a panic for individuals that weigh more than boat can hold")
+		}
+	}()
+	BoatsNeededForEvacuation([]int{200, 250, 300, 301}, 300)
+}
+
+func BenchmarkBoatsNeededForEvacuation(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			BoatsNeededForEvacuation(tc.weights, tc.k)
+		}
+	}
+}