Thời Gian Cần Thiết Để Thông Báo Cho Tất Cả Nhân Viên Trong C++

Giả sử công ty có n nhân viên với ID duy nhất từ 0 đến n-1. Trưởng công ty có headID. Mỗi nhân viên có một quản lý trực tiếp trong mảng manager, manager[i] là quản lý của nhân viên i, manager[headID] = -1. Mối quan hệ cấp bậc hình thành cấu trúc cây. Trưởng công ty muốn thông báo tin tức khẩn cho tất cả nhân viên. Anh ấy thông báo cho cấp dưới trực tiếp, họ tiếp tục lan truyền. Nhân viên i cần informTime[i] phút để thông báo cho tất cả cấp dưới trực tiếp (sau informTime[i] phút, cấp dưới bắt đầu lan truyền). Tìm tổng số phút cần thiết để thông báo cho tất cả nhân viên.

Ví dụ: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0] → đầu ra 1.

Để giải quyết, chúng ta làm theo các bước:

• ret := 0.

• Tạo mảng đồ thị graph kích thước n, root := -1.

• Với i từ 0 đến manager.size()-1: u = manager[i], v = i. Nếu u == -1: root = v; continue; graph[u].push_back(v).

• Tạo queue q, đẩy root vào q, tạo mảng time kích thước n.

• Khi q không rỗng: curr = q.front(); q.pop(); nếu graph[curr] rỗng thì continue; với mỗi con trong graph[curr]: q.push(con); time[con] = time[curr] + informTime[curr].

• Với i từ 0 đến n-1: ret = max(ret, time[i]).

• Trả về ret.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        int ret = 0;
        vector <int> graph[n];
        int root = -1;
        for(int i = 0; i < manager.size(); i++){
            int u = manager[i];
            int v = i;
            if(u == -1) {
                root = v;
                continue;
            }
            graph[u].push_back(v);
        }
        queue <int> q;
        q.push(root);
        vector <int> time(n);
        while(!q.empty()){
            int curr = q.front();
            q.pop();
            if(!graph[curr].size()) continue;
            for(int i = 0; i < graph[curr].size(); i++){
                q.push(graph[curr][i]);
                time[graph[curr][i]] = time[curr] + informTime[curr];
            }
        }
        for(int i = 0; i < n; i++) ret = max(ret, time[i]);
        return ret;
    }
};

int main(){
    vector<int> v = {2,2,-1,2,2,2}, v1 = {0,0,1,0,0,0};
    Solution ob;
    cout << (ob.numOfMinutes(6, 2, v, v1));
}

Đầu vào

6 2 [2,2,-1,2,2,2] [0,0,1,0,0,0]

Đầu ra

1