2023-07-16 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's July LeetCoding Challenge with cpp.

July LeetCoding Challenge 16

Description

Smallest Sufficient Team

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]

 

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.

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
  void solve(
    int skill,
    int mask,
    const vector<vector<int>> &peopleWithSkill,
    const vector<int> &peopleMask,
    vector<int> &current,
    vector<int> &answer
  ) {
    if(skill == peopleWithSkill.size()) {
      if(answer.empty() || current.size() < answer.size()) {
        answer = current;
      }
      return;
    }
    if((1 << skill) & mask) {
      solve(skill + 1, mask, peopleWithSkill, peopleMask, current, answer);
      return;
    }
    for(int i = 0; i < peopleWithSkill[skill].size(); ++i) {
      int newMask = mask | peopleMask[peopleWithSkill[skill][i]];
      current.push_back(peopleWithSkill[skill][i]);
      solve(skill + 1, newMask, peopleWithSkill, peopleMask, current, answer);
      current.pop_back();
    }
  }
public:
  vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
    map<string, int> mp;
    for(int i = 0; i < req_skills.size(); ++i) {
      mp[req_skills[i]] = i;
    }
    vector<int> peopleMask(people.size());
    vector<vector<int>> peopleWithSkill(req_skills.size());
    for(int i = 0; i < people.size(); ++i) {
      for(int j = 0; j < people[i].size(); ++j) {
        int skill = mp[people[i][j]];
        peopleMask[i] |= (1 << skill);
        peopleWithSkill[skill].push_back(i);
      }
    }

    vector<int> answer;
    vector<int> current;
    solve(0, 0, peopleWithSkill, peopleMask, current, answer);
    return answer;
  }
};

// Accepted
// 38/38 cases passed (376 ms)
// Your runtime beats 34.19 % of cpp submissions
// Your memory usage beats 97.42 % of cpp submissions (8.8 MB)
Algorithm