惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

V
Visual Studio Blog
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
T
The Blog of Author Tim Ferriss
宝玉的分享
宝玉的分享
The Register - Security
The Register - Security
D
Docker
The Cloudflare Blog
A
About on SuperTechFans
Microsoft Security Blog
Microsoft Security Blog
Recent Announcements
Recent Announcements
月光博客
月光博客
B
Blog RSS Feed
博客园 - 【当耐特】
The GitHub Blog
The GitHub Blog
B
Blog
IT之家
IT之家
美团技术团队
Engineering at Meta
Engineering at Meta
C
Check Point Blog
云风的 BLOG
云风的 BLOG
Last Week in AI
Last Week in AI
G
Google Developers Blog
MongoDB | Blog
MongoDB | Blog
Microsoft Azure Blog
Microsoft Azure Blog
S
SegmentFault 最新的问题
V
V2EX
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
Apple Machine Learning Research
Apple Machine Learning Research
U
Unit 42
H
Help Net Security
雷峰网
雷峰网
人人都是产品经理
人人都是产品经理
博客园 - 司徒正美
Stack Overflow Blog
Stack Overflow Blog
博客园 - Franky
PCI Perspectives
PCI Perspectives
J
Java Code Geeks
CTFtime.org: upcoming CTF events
CTFtime.org: upcoming CTF events
M
MIT News - Artificial intelligence
腾讯CDC
A
Arctic Wolf
C
CERT Recently Published Vulnerability Notes
量子位
C
CXSECURITY Database RSS Feed - CXSecurity.com
Latest news
Latest news
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
The Hacker News
The Hacker News
有赞技术团队
有赞技术团队
Schneier on Security
Schneier on Security
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻

博客园 - 北叶青藤

2096. Step-By-Step Directions From a Binary Tree Node to Another Find path from root to a target node in Binary Tree When Dijkstra Algorithm Should be Use? 1188. Design Bounded Blocking Queue 1115. Print FooBar Alternately 1114. Print in Order 1242. Web Crawler Multithreaded Python Multi-threading bot ip Log Rate Limiter Same Word of HTML Labels Most Frequent Call Chain remove prefix in a words list 1102. Path With Maximum Minimum Value Property Booking Optimizer minimum number 755. Pour Water Keyword Tagging in Reviews with Overlapping Matches Retryer Function Implementation Print the terrain Split stay Task scheduling problem 滑雪问题 845. Longest Mountain in Array 723. Candy Crush 1539. Kth Missing Positive Number 1650. Lowest Common Ancestor of a Binary Tree III 424. Longest Repeating Character Replacement 843. Guess the Word 551. Student Attendance Record I
1125. Smallest Sufficient Team
北叶青藤 · 2026-02-23 · via 博客园 - 北叶青藤

In a project, you have a list of required skills req_skills, and a list of people. The ith person people[i] contains a list of skills that the person has.

Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill. We can represent these teams by the index of each person.

  • For example, team = [0, 1, 3] represents the people with skills people[0]people[1], and people[3].

Return any sufficient team of the smallest possible size, represented by the index of each person. You may return the answer in any order.

It is guaranteed an answer exists.

Example 1:

Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
Output: [0,2]

Example 2:

Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]

This is a classic Shortest Path problem on a graph, but because we are dealing with a small number of required skills (up to 16), we can view it as a Dynamic Programming problem with Bitmasking.

The Logic

We represent the "set of skills" as a binary number (a bitmask).

  • If the required skills are ["java", "python", "react"], the mask 111 (7 in decimal) represents having all three.

  • The mask 010 (2 in decimal) represents having only "python".

We want to find the smallest number of people whose combined bitmasks equal the target mask (all skills).

 1 class Solution:
 2     def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
 3         n = len(req_skills)
 4         # Map skill name to its bit position
 5         skill_to_idx = {skill: i for i, skill in enumerate(req_skills)}
 6         target_mask = (1 << n) - 1
 7         
 8         # dp[mask] = list of indices of people who cover those skills
 9         # Initialize with the empty set for mask 0
10         dp = {0: []}
11         
12         for i, person_skills in enumerate(people):
13             # Convert current person's skills into a bitmask
14             current_person_mask = 0
15             for skill in person_skills:
16                 if skill in skill_to_idx:
17                     current_person_mask |= (1 << skill_to_idx[skill])
18             
19             # Try to combine this person with all skill sets we've found so far
20             # We iterate over a copy of keys to avoid "dictionary changed size during iteration"
21             for mask, team in list(dp.items()):
22                 new_mask = mask | current_person_mask
23                 
24                 # If we found a new skill combination OR a shorter way to get an existing one
25                 if new_mask not in dp or len(dp[new_mask]) > len(team) + 1:
26                     dp[new_mask] = team + [i]
27                     
28         return dp[target_mask]