558. Smallest Sufficient Team (Bitmask DP)

Given a list of required skills and a list of people (each with a subset of those skills), form the smallest team that collectively covers every required skill, and return the size of that smallest team (or -1 if impossible). Represent skill sets as bitmasks. The input is JSON {skills, people} where people is a list of skill-name lists.

Input: JSON {skills, people}.

Output: Integer — the minimum team size, or -1.

Examples

Input: {"skills":["java","nodejs","reactjs"],"people":[["java"],["nodejs"],["nodejs","reactjs"]]}
Output: 2
Explanation: Person 0 plus person 2 covers all skills.

Input: {"skills":["a","b"],"people":[["a","b"]]}
Output: 1
Explanation: One person covers both.

Input: {"skills":["a"],"people":[["a"],["a"]]}
Output: 1
Explanation: Either person suffices.

Constraints

• 1<=skills<=16
• 1<=people<=60

Asked by