All problems

Fewest Safety Cabinets

Hard · backtracking

A laboratory stores its chemical jars in safety cabinets. The list volumes gives the shelf space each jar takes, in litres: jar i needs volumes[i] litres. Every cabinet has capacity litres of shelf space in total, and no jar is bigger than that.

Some pairs of chemicals react dangerously. The list clashes holds pairs [a, b] of jar numbers, and jars a and b must never be stored in the same cabinet. A pair may be listed more than once or in either order, and jars not named in any pair can share a cabinet freely.

Every jar must go into exactly one cabinet, and the jars in a cabinet must not use more than capacity litres together. Return the fewest cabinets that are enough to store all the jars.

Examples

Example 1

Input: volumes = [4, 4, 4, 4, 4], capacity = 10, clashes = []

Output: 3

Two jars of 4 litres fit in a cabinet (8 litres) but three do not (12), so five jars need two full cabinets and a third one for the last jar.

Example 2

Input: volumes = [2, 2, 2], capacity = 10, clashes = [[0, 1], [1, 2], [0, 2]]

Output: 3

The jars would all fit together, but every pair clashes, so each needs its own cabinet.

Example 3

Input: volumes = [6, 5, 4, 3, 2], capacity = 10, clashes = [[0, 1]]

Output: 2

The jars take 20 litres, so two cabinets are the least possible. The 6 and 4 fill one cabinet and the 5, 3 and 2 fill the other, which also keeps jars 0 and 1 apart.

Constraints