Problem Brief

Package Delivery System

INTERNOA

Each shipment scenario has a list of truck capacities and a list of package weights.

A truck may deliver any package whose weight does not exceed its current capacity. After a successful delivery, that truck's capacity becomes floor(capacity / 2). Determine whether every package in each scenario can be delivered using the available trucks.

Return an int[] where each entry is 1 if the corresponding scenario is feasible and 0 otherwise.

1Example 1

Input

truckCapacities = [[7]], packageWeights = [[4, 3]]

Output

[1]

Explanation

The single truck delivers package 4, its capacity drops to 3, and it can still deliver package 3. The scenario is feasible.

Constraints

Limits and guarantees your solution can rely on.

The number of scenarios and the lengths of the nested arrays can be large, so the solution should avoid brute-force backtracking over all assignments.

Draft autosaves locally

public int[] canDeliverAllPackages(int[][] truckCapacities, int[][] packageWeights) {
  // write your code here
}

Input

truckCapacities

[[7]]

packageWeights

[[4, 3]]

Output

[1]