You are building a simplified “Q&A matching” feature.
You have:
-
people
:
N
people, where person
i
has a set of expertise tags
P[i]
.
-
questions
:
M
questions, where question
j
has a set of tags
Q[j]
and an integer priority
prio[j]
(larger means more important).
A person i can be assigned to answer a question j if they share at least one tag:
P[i]∩Q[j]=∅
Each person can answer at most one question, and each question can be answered by at most one person.
Task
Compute an assignment of people to questions that:
-
Maximizes
the number of answered questions.
-
Subject to (1),
maximizes
the total priority sum of answered questions.
Return:
-
the maximum number of matched (answered) questions
-
the maximum achievable total priority under that maximum match count
Input/Output format (you may choose a reasonable one)
-
Tags are strings.
-
Total number of tags across all people/questions can be large.
Follow-ups
-
Describe a brute-force approach and its complexity.
-
Improve the time complexity using a hash-based index (e.g.,
tag -> list of people/questions
).
-
If processing questions in priority order, explain how a priority queue could help in your implementation.