เวลาที่จำเป็นในการแจ้งพนักงานทุกคนในภาษา C++

สมมติว่าเรามีบริษัทที่มีพนักงาน n คนซึ่งมี ID เฉพาะสำหรับพนักงานแต่ละคน รหัสเหล่านี้มีตั้งแต่ 0 ถึง n - 1 หัวหน้าบริษัทมีคือรหัสที่มีรหัสประจำตัว พนักงานแต่ละคนมีผู้จัดการโดยตรงหนึ่งคนในอาร์เรย์ผู้จัดการโดยที่ manager[i] เป็นผู้จัดการโดยตรงของพนักงานคนที่ i ผู้จัดการ[headID] =-1 นอกจากนี้ยังรับประกันได้ว่าความสัมพันธ์ใต้บังคับบัญชามีโครงสร้างเหมือนต้นไม้ หัวหน้าบริษัทต้องการแจ้งข่าวด่วนให้พนักงานทุกคนของบริษัททราบ เขาสามารถแจ้งผู้ใต้บังคับบัญชาโดยตรงและจะแจ้งผู้ใต้บังคับบัญชาและอื่น ๆ จนกว่าพนักงานทุกคนจะรู้ข่าวด่วน พนักงานคนที่ i ต้องการ informTime[i] minutes เพื่อแจ้งผู้ใต้บังคับบัญชาโดยตรงทั้งหมดของเขา (ดังนั้นหลังจาก informTime[i] นาที ผู้ใต้บังคับบัญชาโดยตรงทั้งหมดของเขาสามารถเริ่มกระจายข่าวได้) เราต้องหาจำนวนนาทีที่ต้องแจ้งข่าวด่วนให้พนักงานทุกคนทราบ ดังนั้นหากอินพุตเป็นเหมือน n =6, headID =2, manager =[2,2,-1,2,2,2], infromTime =[0,0,1,0,0,0] แล้วผลลัพธ์ จะเป็น 1.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ยกเลิก :=0

• กำหนดอาร์เรย์ที่เรียกว่ากราฟขนาด n ตั้งค่ารูท :=-1

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของอาร์เรย์ผู้จัดการ

  • u :=จัดการ[i] และ v :=i

  • ถ้าคุณเป็น -1 ให้ตั้งค่า root :=v และทำซ้ำต่อไป

  • แทรก v ลงในกราฟ[u]

• กำหนดคิว q แทรกรูทลงใน q และกำหนดอาร์เรย์ที่เรียกว่าเวลา ขนาด n

• จนกว่า q จะไม่ว่าง

  • curr :=องค์ประกอบด้านหน้าของ q และลบองค์ประกอบด้านหน้าออกจาก q

  • หากขนาดของรายการกราฟ[curr] เป็น 0 ให้ข้ามไปที่การวนซ้ำถัดไป

  • สำหรับผมอยู่ในช่วง 0 ถึงขนาดของรายการกราฟ[curr]

    • แทรกกราฟ[curr, i] ลงใน q

    • time[graph[curr, i]] :=เวลา[curr] + informTime[curr]

• สำหรับฉันในช่วง 0 ถึง n – 1:ret :=สูงสุดของ ret และเวลา[i]

• รีเทิร์น

ตัวอย่าง (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;
   }
};
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