0717HardArrayDynamic ProgrammingBit ManipulationBitmask

Smallest Crew Cleared For The Job

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(P * 2^S * S) for P candidates and S certificates: each candidate is offered to every cover reached so far, and copying an index list costs O(S) because a smallest group never exceeds S members.Space O(2^S * S) for one index list per reachable cover.

There are at most sixteen certificates, so a set of them fits in an integer with one bit per certificate, and a candidate becomes the mask of the bits they hold. Keep a table from cover to the best group reaching that cover and extend it one candidate at a time, in index order: for every cover already reached, or the group with that candidate joining it, and store the better of the old and new entries, judging first on group size and then on the index list itself. Skipping a candidate who adds no new bit is safe, since dropping such a member from a group leaves it cleared and smaller. Taking candidates in increasing index keeps every stored list sorted and keeps the comparison stable as later members join, so the entry for the full cover at the end is the answer.

Pythonentry point: smallest_crew

def smallest_crew(needed, crew):
    # One bit per needed certificate, so a candidate is a bitmask and a crew's cover
    # is the union of its members' masks.  Walk the candidates in index order and keep,
    # for every cover reached so far, the single best crew that reaches it: fewest
    # members first, then the smaller index list.  Because candidates are taken in
    # increasing index, every stored crew grows by the same later index, so the better
    # of two covers stays better after any further member joins.
    # Time O(P * 2^S * S) for P candidates and S certificates; space O(2^S * S).
    slot = {}
    for i, cert in enumerate(needed):
        slot[cert] = i
    full = (1 << len(needed)) - 1

    best = {0: ()}
    for who, held in enumerate(crew):
        mask = 0
        for cert in held:
            mask |= 1 << slot[cert]
        if mask == 0:
            continue
        for cover, team in list(best.items()):
            merged = cover | mask
            if merged == cover:
                continue
            grown = team + (who,)
            current = best.get(merged)
            if current is None or (len(grown), grown) < (len(current), current):
                best[merged] = grown
    return list(best[full])

The obvious version

Try groups of candidates by size, smallest first, and within a size in index order, returning the first group that holds every needed certificate. Exponential in the number of candidates, so it only runs on a short candidate list, but it makes no use of masks or tables.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_smallest_crew(needed, crew):
    from itertools import combinations

    wanted = set(needed)
    for size in range(len(crew) + 1):
        for pick in combinations(range(len(crew)), size):
            covered = set()
            for who in pick:
                covered.update(crew[who])
            if wanted <= covered:
                return list(pick)
    return []

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in