C++ में सभी कर्मचारियों को सूचित करने के लिए आवश्यक समय

मान लीजिए एक कंपनी में n कर्मचारी हैं जिनमें प्रत्येक कर्मचारी के लिए एक यूनिक ID है। ये IDs 0 से n-1 तक हैं। कंपनी का हेड headID वाला है। प्रत्येक कर्मचारी का एक डायरेक्ट मैनेजर होता है जो मैनेजर ऐरे में दिया गया है जहां manager[i] i-वें कर्मचारी का डायरेक्ट मैनेजर है, manager[headID] = -1। यह भी गारंटी है कि सबऑर्डिनेशन रिलेशनशिप्स ट्री-लाइक स्ट्रक्चर हैं। यहां कंपनी का हेड कंपनी के सभी कर्मचारियों को एक अर्जेंट खबर के बारे में सूचित करना चाहता है। वह अपने डायरेक्ट सबऑर्डिनेट्स को सूचित कर सकता है और वे अपने सबऑर्डिनेट्स को सूचित करेंगे और इसी तरह जब तक सभी कर्मचारी अर्जेंट खबर के बारे में नहीं जान जाते। i-वें कर्मचारी को अपने सभी डायरेक्ट सबऑर्डिनेट्स को सूचित करने के लिए informTime[i] मिनट्स की आवश्यकता होती है (इसलिए informTime[i] मिनट्स के बाद, उसके सभी डायरेक्ट सबऑर्डिनेट्स खबर फैलाना शुरू कर सकते हैं)। हमें सभी कर्मचारियों को अर्जेंट खबर के बारे में सूचित करने के लिए आवश्यक मिनट्स की संख्या ढूंढनी है। उदाहरण के लिए, अगर इनपुट है n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0], तो आउटपुट 1 होगा।

इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:

• ret := 0

• साइज n का एक ऐरे graph डिफाइन करें, root := -1 सेट करें

• i को 0 से मैनेजर ऐरे के साइज तक लूप करें:

  • u := manager[i] और v := i

  • अगर u -1 है, तो root := v सेट करें, और अगले इटरेशन पर जाएं

  • v को graph[u] में इंसर्ट करें

• एक क्यू q डिफाइन करें, root को q में इंसर्ट करें, और साइज n का एक ऐरे time डिफाइन करें

• जब तक q खाली नहीं है:

  • curr := q का फ्रंट एलिमेंट, और q से फ्रंट एलिमेंट डिलीट करें

  • अगर graph[curr] की लिस्ट का साइज 0 है, तो अगले इटरेशन पर जाएं

  • i को 0 से graph[curr] की लिस्ट के साइज तक लूप करें:

    • graph[curr][i] को q में इंसर्ट करें

    • time[graph[curr][i]] := time[curr] + informTime[curr]

• i को 0 से n-1 तक लूप करें: ret := ret और time[i] का मैक्स

• ret लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्न इम्प्लीमेंटेशन देखें:

#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));
}

इनपुट

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

आउटपुट

1