Show problems as
Classic problem #1125HardArrayDynamic ProgrammingBit ManipulationBitmask

Smallest Sufficient Team

Real-world version: Smallest Crew Cleared For The Job
Tracked in this browser only
Read Smallest Sufficient Team on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A shutdown job may only go ahead once every certificate in needed is held by somebody on the crew. crew[i] lists the certificates that candidate i holds. A group of candidates is cleared for the job when, for every certificate in needed, at least one candidate in the group holds it. One candidate may hold several certificates, and a candidate may hold none at all.

Return the indices of the candidates in a cleared group of the smallest possible size, listed in increasing order.

Two different groups may both be smallest, so exactly one answer is asked for: among the cleared groups of the smallest size, return the one whose list of indices is smaller when the two lists are read side by side from the front, that is, the one with the smaller index at the first place where the lists differ.

Examples

Example 1

Input
needed = ["weld", "rig", "hoist"], crew = [["weld"], ["rig", "hoist"], ["weld", "rig", "hoist"]]
Output
[2]

Candidate 2 holds weld, rig and hoist, which is every certificate the job needs, so the group holding just that one candidate is cleared.

Example 2

Input
needed = ["weld", "rig", "hoist", "crane"], crew = [["weld", "rig"], ["hoist", "crane"], ["weld", "rig", "hoist"]]
Output
[0, 1]

Candidates 0 and 1 between them hold weld, rig, hoist and crane, so that pair is cleared. Candidates 1 and 2 are also a cleared pair, and the tie-break reads the two lists side by side: 0 is smaller than 1 at the first place they differ.

Example 3

Input
needed = ["weld", "rig"], crew = [[], ["weld"], ["rig"]]
Output
[1, 2]

Candidate 0 holds no certificates. Candidate 1 holds weld and candidate 2 holds rig, so that pair covers both needed certificates.

Constraints

  • 1 <= needed.length <= 16
  • 1 <= needed[i].length <= 16
  • needed[i] consists of lowercase English letters.
  • The certificates in needed are all different.
  • 1 <= crew.length <= 60
  • 0 <= crew[i].length <= 16
  • 1 <= crew[i][j].length <= 16
  • crew[i][j] consists of lowercase English letters.
  • The certificates listed for one candidate are all different.
  • Every certificate a candidate holds appears in needed.
  • At least one group of candidates is cleared for the job.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def smallest_crew(needed: list[str], crew: list[list[str]]) -> list[int]:
Java
public int[] smallestCrew(String[] needed, List<List<String>> crew)

More on the same topics