OneNoughtOne
0/364
Loading content...
During an emergency evacuation scenario, you are tasked with transporting a group of people to safety using rescue vessels. You are provided with an array passengers where passengers[i] represents the body weight of the i-th person waiting to be evacuated, and a value capacity representing the maximum weight that each rescue vessel can safely carry.
Each rescue vessel has a strict safety regulation: it can transport at most two people at once, and the combined weight of those passengers must not exceed the vessel's capacity. You have access to an unlimited supply of identical rescue vessels, each with the same weight capacity.
Your objective is to determine the minimum number of rescue vessels required to evacuate all passengers safely. Every person must be transported exactly once, and no vessel may be overloaded beyond its capacity limit.
The challenge lies in optimally pairing passengers to minimize the total number of vessels used while respecting the weight constraints and the two-person-per-vessel limitation.
passengers = [1,2]
capacity = 31Explanation
Both passengers can share a single vessel since their combined weight (1 + 2 = 3) does not exceed the capacity of 3. Thus, only 1 vessel is needed.
passengers = [3,2,2,1]
capacity = 33Explanation
Optimal allocation: Vessel 1 carries passengers with weights (1, 2), Vessel 2 carries the passenger with weight (2) alone, and Vessel 3 carries the passenger with weight (3) alone. The pair (1,2) sums to 3 which equals capacity, while the heavier passengers cannot be paired without exceeding the limit.
passengers = [3,5,3,4]
capacity = 54Explanation
No two passengers can share a vessel because every possible pair would exceed the capacity of 5. Passengers with weights 3+3=6, 3+4=7, 3+5=8, 4+5=9, and 5+3=8 all exceed 5. Therefore, each passenger requires their own vessel, resulting in 4 vessels total.
Constraints