thảo luận Leetcode mỗi ngày

use std::collections::HashMap;
impl Solution {
    pub fn longest_subsequence(arr: Vec<i32>, difference: i32) -> i32 {
        let mut dp = HashMap::new();
        let mut res = 1;
        arr.iter().for_each(|&x| {
            let c = dp.get(&(x - difference)).unwrap_or(&0) + 1;
            dp.insert(x, c);
            res = res.max(c);
        });
        res
    }
}

class Solution {
public:
    static bool cmp(vector<int>& x,vector<int>& y){
        return x[1] < y[1];
    }
    int maxValue(vector<vector<int>>& events, int k) {
        int n = events.size();
        int dp[n+1][k+1];
        memset(dp,0,sizeof dp);
        sort(events.begin(),events.end(),cmp);
        for (int i = 1; i <= n; i++){
            auto cur = events[i-1]; // current event
            int st = cur[0], ed = cur[1], val = cur[2];
            // start time, end time, value
            int l = 1, r = i - 1;
            while (l < r){
                int mid = l + (r - l + 1) / 2;
                if (events[mid-1][1] < st){
                    l = mid;
                }
                else r = mid - 1;
            }
            int last = r;
            if (r > 0){
                if (events[r-1][1] >= st) last = 0;
            }
            for (int j = 1; j <= k; j++){
                dp[i][j] = max(dp[i-1][j],dp[last][j-1] + val);
            }
        }
        return dp[n][k];
    }
};

class Solution {
public:
    int maxValue(vector<vector<int>>& events, int k) {
        //sort by start date
        sort(events.begin(), events.end(),
                    [] (const auto &a, const auto &b) {return a[0] < b[0];});
        vector<pair<int,priority_queue<int, vector<int>, greater<int>>>> dp(events.size());
        for (int i = events.size() - 1; i >= 0; --i) {
            auto it = upper_bound(events.begin() + i + 1, events.end(), events[i][1],
                                    [] (const auto &val, const auto &element) {return val < element[0];});
            if (it != events.end()) {
                int j = distance(events.begin(), it);
                dp[i] = dp[j];
            }
            
            dp[i].second.push(events[i][2]);
            dp[i].first += events[i][2];
            if (dp[i].second.size() > k) {
                dp[i].first -= dp[i].second.top();
                dp[i].second.pop();
            }

            if (i < events.size() - 1 && dp[i].first < dp[i+1].first) {
                dp[i] = dp[i+1];
            }
        }
        return dp.front().first;
    }
};

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        events.sort(key=lambda x: x[1])
        @lru_cache(None)
        def recurse(k: int, i: int, j: int) -> int:
            if i >= len(events) or k <= 0:
                return 0
            include, exclude = 0, 0
            if j < 0 or events[j][1] < events[i][0]:
                include = recurse(k - 1, i + 1, i) + events[i][2]
            exclude = recurse(k, i + 1, j)
            return max(include, exclude)
        return recurse(k, 0, -1)

class Solution {
   private:
    vector<vector<int>> memo;
    int recurse(vector<vector<int>> &events, int k, int i) {
        if (i >= events.size() || k < 0) return 0;
        if (memo[k][i] != -1) return memo[k][i];
        int next = partition_point(begin(events) + i + 1, end(events),
                                   [&](const auto &e) { return e[0] <= events[i][1]; }) -
                   begin(events);
        int in = recurse(events, k - 1, next) + events[i][2];
        int ex = recurse(events, k, i + 1);
        return memo[k][i] = max(in, ex);
    }
   public:
    int maxValue(vector<vector<int>> &events, int k) {
        memo = vector<vector<int>>(k, vector<int>(events.size(), -1));
        sort(begin(events), end(events), [](const auto &a, const auto &b) { return a[0] < b[0]; });
        return recurse(events, k - 1, 0);
    }
};

class Solution {
public:
    const int N = 17;
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        int m = req_skills.size(), n = people.size();
        map<string, int> mp;
        int dp[1<<m];
        vector<vector<int>> res(1<<m);
        memset(dp,N,sizeof dp); // dp[i] là số người ít nhất để có trọn vẹn
        // các skill trong mask i
        dp[0] = 0;
        for (int i = 0; i < m; i++){
            mp[req_skills[i]] = i;
            // đánh dấu cho skill i
        }
        for (int i = 0; i < n; i++){
            int mask = 0;
            for (int j = 0; j < people[i].size(); j++){
                mask |= (1 << (mp[people[i][j]]));
            }
            // mask thể hiện các skill mà người i đang sở hữu
            for (int j = (1 << m) - 1; j >= 0; j--){
                // j | mask thể hiện các kĩ năng được sỡ hữu
                // sau khi cho thêm người i vào
                // dòng lệnh if ở dưới kiểm tra xem nếu thêm
                // người i vào thì có thể tối ưu cho dp[j|mask] được không
                if (dp[j|mask] > dp[j] + 1){
                    dp[j|mask] = dp[j] + 1;
                    // kết quả của j|mask chính là kết quả của j cộng thêm
                    // người thứ i nếu cập nhật thành công
                    res[j|mask] = res[j];
                    res[j|mask].push_back(i);
                }
            }
        }
        return res[(1<<m)-1]; // trả về kết quả cho toàn bộ skill
        // (1 << m) - 1 thì tất cả các bit từ 0 -> m - 1 đều được bật
    }
};

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        toInt = {}
        for i, skill in enumerate(req_skills):
            toInt[skill] = i

        for i in range(len(people)):
            state = 0
            for j in range(len(people[i])):
                state += 1 << toInt[people[i][j]]
            people[i] = state

        final_state = (1 << len(req_skills)) - 1
        states = {0 : []}
        while True:
            for state, group in list(states.items()):
                for i in range(len(people)):
                    new_state = state | people[i]
                    if new_state in states: continue
                    if new_state == final_state:
                        return group + [i]
                    states[new_state] = group + [i]

type SortedSkill = { skill: string; indices: number[] };
function getRequiredSkillMap(
  requiredSkills: string[]
): Record<string, number[]> {
  return requiredSkills.reduce<Record<string, number[]>>((acc, curr) => {
    acc[curr] = [];
    return acc;
  }, {});
}

function getSortedRequiredSkill(
  requiredSkillMap: Record<string, number[]>,
  people: string[][]
): SortedSkill[] {
  const arr = Object.entries(requiredSkillMap).map(([skill, indices]) => ({
    skill,
    indices,
  }));

  arr.sort((a, b) => (a.indices.length < b.indices.length ? -1 : 1));

  for (let i = 0; i < arr.length; i++) {
    arr[i].indices.sort((a, b) =>
      people[a].length < people[b].length ? 1 : -1
    );
  }

  return arr;
}

function getEmptyMap(skills: string[]): Record<string, number> {
  return skills.reduce<Record<string, number>>((acc, curr) => {
    acc[curr] = 0;
    return acc;
  }, {});
}

function solve(
  idx: number,
  selected: number[],
  fillMap: Record<string, number>,
  sortedRequireSkills: SortedSkill[],
  people: string[][]
): number[] {
  if (idx >= sortedRequireSkills.length) {
    return [...selected];
  }

  const skill = sortedRequireSkills[idx];

  // skip
  if (fillMap[skill.skill]) {
    const r = solve(idx + 1, selected, fillMap, sortedRequireSkills, people);
    return r;
  }

  let res: number[] = [];

  for (let i = 0; i < skill.indices.length; i++) {
    const personIdx = skill.indices[i];
    const currPersonSkills = people[personIdx];

    selected.push(personIdx);
    for (let j = 0; j < people[personIdx].length; j++) {
      fillMap[currPersonSkills[j]]++;
    }
    const s = solve(idx + 1, selected, fillMap, sortedRequireSkills, people);
    selected.pop();
    for (let j = 0; j < people[personIdx].length; j++) {
      fillMap[currPersonSkills[j]]--;
    }

    if (res.length === 0 || s.length < res.length) {
      res = s;
    }
  }

  return res;
}

function smallestSufficientTeam(
  requiredSkills: string[],
  people: string[][]
): number[] {
  const requiredSkillMap = getRequiredSkillMap(requiredSkills);

  for (let i = 0; i < people.length; i++) {
    const skills = people[i];
    for (let j = 0; j < skills.length; j++) {
      const skill = skills[j];
      if (!requiredSkillMap[skill]) continue;
      requiredSkillMap[skill].push(i);
    }
  }

  const sortedRequireSkills = getSortedRequiredSkill(requiredSkillMap, people);

  console.log(sortedRequireSkills);

  return solve(0, [], getEmptyMap(requiredSkills), sortedRequireSkills, people);
}

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        all_skill_mask = (1 << len(req_skills)) - 1
        people_skill_mask_map = dict()
        req_skill_index_map = dict()

        for skill_index, skill in enumerate(req_skills):
            req_skill_index_map[skill] = skill_index

        for people_index, people_skills in enumerate(people):
            people_skill_mask = 0
            for skill in people_skills:
                people_skill_mask |= (1 << req_skill_index_map[skill])
            people_skill_mask_map[people_index] = people_skill_mask

        queue = deque([(0, 0)])
        visited_skill_mask = {0}
        smallest_team_mask = 0

        while queue:
            skill_mask, people_mask = queue.popleft()

            if skill_mask == all_skill_mask:
                smallest_team_mask = people_mask
                break

            for next_people_index, next_skill_mask in people_skill_mask_map.items():
                new_skill_mask = skill_mask | next_skill_mask
                next_people_mask = 1 << next_people_index

                if new_skill_mask in visited_skill_mask:
                    continue
                if next_people_mask & people_mask:
                    continue

                visited_skill_mask.add(new_skill_mask)
                new_people_mask = people_mask | next_people_mask
                queue.append((new_skill_mask, new_people_mask))


        result = []   

        for people_index in range(len(people)):
            people_mask = 1 << people_index
            if people_mask & smallest_team_mask:
                result.append(people_index)
        
        return result