Minimal Employee Assignment for Projects

You are given a set of projects and a set of employees. Each project has an id and a list of required skills. Each employee has an id and a list of skills. Your task is to assign the minimum number of employees to each project such that the union of their skills covers all the required skills for that project. If a project cannot be fully covered by the available employees, then it should not be assigned any employees.

The program must read from stdin and output the result to stdout as a JSON object. The output JSON object should have keys corresponding to project IDs (numeric) and values as arrays of employee IDs (strings) assigned to that project.

Note: Use a brute force approach (trying all combinations) since the number of employees and projects will be small. For each project, find a subset of employees with the smallest possible size that covers all required skills.

The required skills in mathematical notation can be expressed as: $$\text{RequiredSkills} \subseteq \bigcup_{e \in S} \text{Skills}(e)$$ where \(S\) is the chosen set of employees for a project.

inputFormat

The input is read from standard input (stdin) and has the following format:

P
project_id1 k1 skill11 skill12 ... skill1k1
project_id2 k2 skill21 skill22 ... skill2k2
...
project_idP kP skillP1 skillP2 ... skillPkP
E
employee_id1 m1 skill11 skill12 ... skill1m1
employee_id2 m2 skill21 skill22 ... skill2m2
...
employee_idE mE skillE1 skillE2 ... skillEmE

- The first line contains an integer P representing the number of projects.
- The next P lines describe each project. Each project line starts with an integer project_id, followed by an integer k (the number of required skills), then k strings each representing a required skill.
- After that, a line with an integer E denotes the number of employees.
- The following E lines describe each employee. Each employee line starts with a string employee_id, followed by an integer m (the number of skills the employee has), then m strings for the skills.

outputFormat

Output a JSON object to standard output (stdout) where keys are the project IDs (as numbers) and values are arrays of employee IDs (as strings) corresponding to the minimal set of employees assigned to that project. Projects that cannot be fully staffed should not appear in the output.

2
1 2 python sql
2 3 javascript css html
4
a 1 python
b 2 python sql
c 2 javascript css
d 2 html css

{"1": ["b"], "2": ["c", "d"]}