Задача: 690. Employee Importance
Сложность: medium

У вас есть структура данных с информацией о сотрудниках, включая уникальный идентификатор сотрудника, значение его важности и идентификаторы его прямых подчиненных.

Вам дан массив сотрудников employees, где:

employees[i].id — это идентификатор i-го сотрудника.
employees[i].importance — значение важности i-го сотрудника.
employees[i].subordinates — список идентификаторов прямых подчиненных i-го сотрудника.
Дан целочисленный id, представляющий идентификатор сотрудника. Верните суммарное значение важности этого сотрудника и всех его прямых и косвенных подчиненных.

Пример:

Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
Output: 11
Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3.
They both have an importance value of 3.
Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.

👨‍💻 Алгоритм:

1⃣Создайте хеш-таблицу emap для быстрого доступа к сотрудникам по их идентификаторам.

2⃣Реализуйте функцию DFS для подсчета общей важности, которая включает важность сотрудника и всех его подчиненных.

3⃣Используйте DFS для вычисления общей важности, начиная с заданного идентификатора сотрудника.

😎 Решение:

class Employee {
    public $id;
    public $importance;
    public $subordinates;
    
    function __construct($id, $importance, $subordinates) {
        $this->id = $id;
        $this->importance = $importance;
        $this->subordinates = $subordinates;
    }
}

class Solution {
    private $emap;
    
    function getImportance($employees, $queryid) {
        $this->emap = [];
        foreach ($employees as $e) {
            $this->emap[$e->id] = $e;
        }
        return $this->dfs($queryid);
    }
    
    private function dfs($eid) {
        $employee = $this->emap[$eid];
        $ans = $employee->importance;
        foreach ($employee->subordinates as $subid) {
            $ans += $this->dfs($subid);
        }
        return $ans;
    }
}

Ставь 👍 и забирай 📚 Базу знаний