Giả sử cho một dự án ta có danh sách kỹ năng yêu cầu req_skills, và danh sách người. Người thứ i people[i] chứa danh sách kỹ năng người đó có.
Bây giờ nhóm đủ kỹ năng (sufficient team) được định nghĩa là tập hợp người sao cho với mọi kỹ năng yêu cầu trong req_skills, có ít nhất một người trong nhóm có kỹ năng đó. Ta có thể biểu diễn các nhóm bằng chỉ số của mỗi người: Ví dụ team là [0, 1, 3] đại diện cho người có kỹ năng people[0], people[1], people[3].
Ta cần tìm nhóm có kích thước nhỏ nhất có thể.
Bạn có thể trả về đáp án theo bất kỳ thứ tự nào. Đảm bảo luôn có đáp án.
Ví dụ, nếu đầu vào là req_skills = ["java","flutter","android"], people = [["java"],["android"],["flutter","android"]], thì đầu ra sẽ là [0,2]
Để giải quyết, ta thực hiện các bước sau:
- dp := một map, thêm danh sách rỗng cho key 0
- key := một map như (value,i) nơi value từ req_skills và i là số
- Với cặp số, người (i, p) từ mảng people:
- current_skill := 0
- Với skill trong p:
- current_skill := current_skill OR 2^key[skill]
- Với cặp (skill_set, members) trong các cặp key-value của dp:
- total_skill := skill_set OR current_skill
- Nếu total_skill bằng skill_set, thì:
- Bỏ qua phần tiếp theo, chuyển sang vòng lặp tiếp theo
- Nếu total_skill không trong dp hoặc kích thước dp[total_skill] > kích thước members + 1, thì:
- dp[total_skill] := members + [i]
- Trả về dp[(1 << len(req_skills)) - 1]
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
class Solution(object): def smallestSufficientTeam(self, req_skills, people): dp = {0:[]} key = {v:i for i,v in enumerate(req_skills)} for i,p in enumerate(people): current_skill = 0 for skill in p: current_skill |= 1< len(members)+1: dp[total_skill] = members + [i] return dp[(1<Đầu vào
["java","flutter","android"] [["java"],["android"],["flutter","android"]]
Đầu ra
[0,2]