Spaceship Equipment Loadout
Jane Street● MediumINTERNONSITE INTERVIEWProblem statement
Choose one fixed subset of spaceship equipment whose total weight does not exceed capacity. Equipment item i mitigates every hazard listed in protections[i]. A test run is fully mitigated when every hazard in that run is covered by at least one selected item.
Exactly five runs are supplied. Maximize the number of fully mitigated runs. Break ties by smaller total equipment weight, then by the lexicographically smaller sorted list of selected equipment names. Return that sorted name list.
Function
optimizeLoadout(capacity: int, equipmentNames: String[], weights: int[], protections: String[][], runs: String[][]) → String[]Examples
Example 1
capacity = 7equipmentNames = ["Armor","Laser","Shield","Net"]weights = [4,3,4,2]protections = [["debris"],["pirates"],["asteroids"],["debris","pirates"]]runs = [["pirates"],["debris"],["asteroids"],["debris","pirates"],["pirates"]]return = ["Net","Shield"]Net and Shield weigh six and fully mitigate all five runs.
Example 2
capacity = 3equipmentNames = ["A","B","C"]weights = [2,2,3]protections = [["pirates"],["debris"],["pirates","debris"]]runs = [["pirates"],["debris"],["pirates","debris"],["asteroids"],["pirates"]]return = ["C"]C is the only feasible single item that fully mitigates both the combined run and the other covered runs.
Constraints
1 <= equipmentNames.length <= 18.weights.length == protections.length == equipmentNames.length.- Equipment names are unique; every weight is positive.
runs.length == 5, and every run contains at least one hazard.- Hazard names and equipment names are non-empty ASCII strings.