Smallest Sufficient Team

// Accepted solution for LeetCode #1125: Smallest Sufficient Team
class Solution {
    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        Map<String, Integer> d = new HashMap<>();
        int m = req_skills.length;
        int n = people.size();
        for (int i = 0; i < m; ++i) {
            d.put(req_skills[i], i);
        }
        int[] p = new int[n];
        for (int i = 0; i < n; ++i) {
            for (var s : people.get(i)) {
                p[i] |= 1 << d.get(s);
            }
        }
        int[] f = new int[1 << m];
        int[] g = new int[1 << m];
        int[] h = new int[1 << m];
        final int inf = 1 << 30;
        Arrays.fill(f, inf);
        f[0] = 0;
        for (int i = 0; i < 1 << m; ++i) {
            if (f[i] == inf) {
                continue;
            }
            for (int j = 0; j < n; ++j) {
                if (f[i] + 1 < f[i | p[j]]) {
                    f[i | p[j]] = f[i] + 1;
                    g[i | p[j]] = j;
                    h[i | p[j]] = i;
                }
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = (1 << m) - 1; i != 0; i = h[i]) {
            ans.add(g[i]);
        }
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}

// Accepted solution for LeetCode #1125: Smallest Sufficient Team
func smallestSufficientTeam(req_skills []string, people [][]string) (ans []int) {
	d := map[string]int{}
	for i, s := range req_skills {
		d[s] = i
	}
	m, n := len(req_skills), len(people)
	p := make([]int, n)
	for i, ss := range people {
		for _, s := range ss {
			p[i] |= 1 << d[s]
		}
	}
	const inf = 1 << 30
	f := make([]int, 1<<m)
	g := make([]int, 1<<m)
	h := make([]int, 1<<m)
	for i := range f {
		f[i] = inf
	}
	f[0] = 0
	for i := range f {
		if f[i] == inf {
			continue
		}
		for j := 0; j < n; j++ {
			if f[i]+1 < f[i|p[j]] {
				f[i|p[j]] = f[i] + 1
				g[i|p[j]] = j
				h[i|p[j]] = i
			}
		}
	}
	for i := 1<<m - 1; i != 0; i = h[i] {
		ans = append(ans, g[i])
	}
	return
}

# Accepted solution for LeetCode #1125: Smallest Sufficient Team
class Solution:
    def smallestSufficientTeam(
        self, req_skills: List[str], people: List[List[str]]
    ) -> List[int]:
        d = {s: i for i, s in enumerate(req_skills)}
        m, n = len(req_skills), len(people)
        p = [0] * n
        for i, ss in enumerate(people):
            for s in ss:
                p[i] |= 1 << d[s]
        f = [inf] * (1 << m)
        g = [0] * (1 << m)
        h = [0] * (1 << m)
        f[0] = 0
        for i in range(1 << m):
            if f[i] == inf:
                continue
            for j in range(n):
                if f[i] + 1 < f[i | p[j]]:
                    f[i | p[j]] = f[i] + 1
                    g[i | p[j]] = j
                    h[i | p[j]] = i
        i = (1 << m) - 1
        ans = []
        while i:
            ans.append(g[i])
            i = h[i]
        return ans

// Accepted solution for LeetCode #1125: Smallest Sufficient Team
/**
 * [1125] Smallest Sufficient Team
 *
 * In a project, you have a list of required skills req_skills, and a list of people. The i^th 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]
 *  
 * Constraints:
 *
 * 	1 <= req_skills.length <= 16
 * 	1 <= req_skills[i].length <= 16
 * 	req_skills[i] consists of lowercase English letters.
 * 	All the strings of req_skills are unique.
 * 	1 <= people.length <= 60
 * 	0 <= people[i].length <= 16
 * 	1 <= people[i][j].length <= 16
 * 	people[i][j] consists of lowercase English letters.
 * 	All the strings of people[i] are unique.
 * 	Every skill in people[i] is a skill in req_skills.
 * 	It is guaranteed a sufficient team exists.
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/smallest-sufficient-team/
// discuss: https://leetcode.com/problems/smallest-sufficient-team/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    // Credit: https://leetcode.com/problems/smallest-sufficient-team/solutions/3039366/just-a-runnable-solution/
    pub fn smallest_sufficient_team(req_skills: Vec<String>, people: Vec<Vec<String>>) -> Vec<i32> {
        let mut skills = std::collections::HashMap::new();
        for (i, skill) in req_skills.iter().enumerate() {
            skills.insert(skill, i);
        }
        let mut people_skill = vec![0; people.len()];
        for (i, person) in people.iter().enumerate() {
            for skill in person {
                let temp = *skills.get(skill).unwrap();
                people_skill[i] |= 1 << temp;
            }
        }
        let s = 1 << req_skills.len();
        let mut dp = vec![std::i32::MAX; s];
        let mut parent = vec![-1; s];
        let mut parent_state = vec![0; s];
        dp[0] = 0;
        for i in 0..(1 << req_skills.len()) {
            for (j, &item) in people_skill.iter().enumerate().take(people.len()) {
                if dp[i] == std::i32::MAX {
                    continue;
                }
                let temp = i | item;
                if dp[temp] > dp[i] + 1 {
                    parent[temp] = j as i32;
                    parent_state[temp] = i;
                    dp[temp] = dp[i] + 1;
                }
            }
        }
        let mut temp = (1 << req_skills.len()) - 1;
        let mut result = vec![];
        while parent[temp] != -1 {
            result.push(parent[temp]);
            temp = parent_state[temp];
        }
        result
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_1125_example_1() {
        let req_skills = vec_string!["java", "nodejs", "reactjs"];
        let people = vec![
            vec_string!["java"],
            vec_string!["nodejs"],
            vec_string!["nodejs", "reactjs"],
        ];
        let result = vec![0, 2];

        assert_eq_sorted!(
            Solution::smallest_sufficient_team(req_skills, people),
            result
        );
    }

    #[test]
    fn test_1125_example_2() {
        let req_skills = vec_string!["algorithms", "math", "java", "reactjs", "csharp", "aws"];
        let people = vec![
            vec_string!["algorithms", "math", "java"],
            vec_string!["algorithms", "math", "reactjs"],
            vec_string!["java", "csharp", "aws"],
            vec_string!["reactjs", "csharp"],
            vec_string!["csharp", "math"],
            vec_string!["aws", "java"],
        ];

        let result = vec![1, 2];

        assert_eq_sorted!(
            Solution::smallest_sufficient_team(req_skills, people),
            result
        );
    }
}

// Accepted solution for LeetCode #1125: Smallest Sufficient Team
function smallestSufficientTeam(req_skills: string[], people: string[][]): number[] {
    const d: Map<string, number> = new Map();
    const m = req_skills.length;
    const n = people.length;
    for (let i = 0; i < m; ++i) {
        d.set(req_skills[i], i);
    }
    const p: number[] = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        for (const s of people[i]) {
            p[i] |= 1 << d.get(s)!;
        }
    }
    const inf = 1 << 30;
    const f: number[] = new Array(1 << m).fill(inf);
    const g: number[] = new Array(1 << m).fill(0);
    const h: number[] = new Array(1 << m).fill(0);
    f[0] = 0;
    for (let i = 0; i < 1 << m; ++i) {
        if (f[i] === inf) {
            continue;
        }
        for (let j = 0; j < n; ++j) {
            if (f[i] + 1 < f[i | p[j]]) {
                f[i | p[j]] = f[i] + 1;
                g[i | p[j]] = j;
                h[i | p[j]] = i;
            }
        }
    }
    const ans: number[] = [];
    for (let i = (1 << m) - 1; i; i = h[i]) {
        ans.push(g[i]);
    }
    return ans;
}