#230HardDynamic Programming· Bitmask DP over Required Skills

Minimum Crews Covering Skills

A film production needs a set of specialist skills (for example "camera", "sound", "stunts"). A pool of freelancers is available and each freelancer masters some skills, possibly including skills the production does not need. Hire as few freelancers as possible so that every required skill is covered by at least one hired person. Return that minimum head count, or `-1` if the whole pool together still misses a required skill.

Input format

`required`: an array of distinct skill names; `people`: an array where `people[i]` lists the skills of freelancer `i`.

Output format

An integer: the minimum number of freelancers, or -1.

Examples

Input: required = ["camera", "sound", "stunts"], people = [["camera"], ["sound", "stunts"], ["camera", "sound"]]

Output: 2

Hiring freelancer 0 (camera) and freelancer 1 (sound, stunts) covers all three skills, and no single person does.

Input: required = ["lights", "cables"], people = [["lights", "cables", "rigging"], ["cables"]]

Output: 1

Freelancer 0 covers both required skills alone.

Input: required = ["drone", "editing"], people = [["editing"], []]

Output: -1

Nobody can fly a drone, so the production cannot be staffed.

Constraints

1 <= required.length <= 16
1 <= people.length <= 60
Skill names are non-empty lowercase strings of length at most 16.
people[i] may be empty and may contain skills that are not required.

#bitmask
#dynamic-programming
#set-cover
#strings
#optimization