Package g2001_2100.s2039_the_time_when_the_network_becomes_idle

Class Solution

java.lang.Object

g2001_2100.s2039_the_time_when_the_network_becomes_idle.Solution

public class Solution
extends Object

2039 - The Time When the Network Becomes Idle.<p>Medium</p> <p>There is a network of <code>n</code> servers, labeled from <code>0</code> to <code>n - 1</code>. You are given a 2D integer array <code>edges</code>, where <code>edges[i] = [u_i, v_i]</code> indicates there is a message channel between servers <code>u_i</code> and <code>v_i</code>, and they can pass <strong>any</strong> number of messages to <strong>each other</strong> directly in <strong>one</strong> second. You are also given a <strong>0-indexed</strong> integer array <code>patience</code> of length <code>n</code>.</p> <p>All servers are <strong>connected</strong> , i.e., a message can be passed from one server to any other server(s) directly or indirectly through the message channels.</p> <p>The server labeled <code>0</code> is the <strong>master</strong> server. The rest are <strong>data</strong> servers. Each data server needs to send its message to the master server for processing and wait for a reply. Messages move between servers <strong>optimally</strong> , so every message takes the <strong>least amount of time</strong> to arrive at the master server. The master server will process all newly arrived messages <strong>instantly</strong> and send a reply to the originating server via the <strong>reversed path</strong> the message had gone through.</p> <p>At the beginning of second <code>0</code>, each data server sends its message to be processed. Starting from second <code>1</code>, at the <strong>beginning</strong> of <strong>every</strong> second, each data server will check if it has received a reply to the message it sent (including any newly arrived replies) from the master server:</p> <ul> <li>If it has not, it will <strong>resend</strong> the message periodically. The data server <code>i</code> will resend the message every <code>patience[i]</code> second(s), i.e., the data server <code>i</code> will resend the message if <code>patience[i]</code> second(s) have <strong>elapsed</strong> since the <strong>last</strong> time the message was sent from this server.</li> <li>Otherwise, <strong>no more resending</strong> will occur from this server.</li> </ul> <p>The network becomes <strong>idle</strong> when there are <strong>no</strong> messages passing between servers or arriving at servers.</p> <p>Return <em>the <strong>earliest second</strong> starting from which the network becomes <strong>idle</strong></em>.</p> <p><strong>Example 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/09/22/quiet-place-example1.png" alt="example 1" /></p> <p><strong>Input:</strong> edges = [[0,1],[1,2]], patience = [0,2,1]</p> <p><strong>Output:</strong> 8</p> <p><strong>Explanation:</strong></p> <p>At (the beginning of) second 0,</p> <ul> <li> <p>Data server 1 sends its message (denoted 1A) to the master server.</p> </li> <li> <p>Data server 2 sends its message (denoted 2A) to the master server.</p> </li> </ul> <p>At second 1,</p> <ul> <li> <p>Message 1A arrives at the master server. Master server processes message 1A instantly and sends a reply 1A back.</p> </li> <li> <p>Server 1 has not received any reply. 1 second (1 < patience[1] = 2) elapsed since this server has sent the message, therefore it does not resend the message.</p> </li> <li> <p>Server 2 has not received any reply. 1 second (1 == patience[2] = 1) elapsed since this server has sent the message, therefore it resends the message (denoted 2B).</p> </li> </ul> <p>At second 2,</p> <ul> <li> <p>The reply 1A arrives at server 1. No more resending will occur from server 1.</p> </li> <li> <p>Message 2A arrives at the master server. Master server processes message 2A instantly and sends a reply 2A back.</p> </li> <li> <p>Server 2 resends the message (denoted 2C).</p> </li> </ul> <p>&hellip;</p> <p>At second 4,</p> <ul> <li>The reply 2A arrives at server 2. No more resending will occur from server 2.</li> </ul> <p>&hellip;</p> <p>At second 7, reply 2D arrives at server 2.</p> <p>Starting from the beginning of the second 8, there are no messages passing between servers or arriving at servers.</p> <p>This is the time when the network becomes idle.</p> <p><strong>Example 2:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/09/04/network_a_quiet_place_2.png" alt="example 2" /></p> <p><strong>Input:</strong> edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]</p> <p><strong>Output:</strong> 3</p> <p><strong>Explanation:</strong> Data servers 1 and 2 receive a reply back at the beginning of second 2.</p> <p>From the beginning of the second 3, the network becomes idle.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>n == patience.length</code></li> <li><code>2 <= n <= 10⁵</code></li> <li><code>patience[0] == 0</code></li> <li><code>1 <= patience[i] <= 10⁵</code> for <code>1 <= i < n</code></li> <li><code>1 <= edges.length <= min(10⁵, n * (n - 1) / 2)</code></li> <li><code>edges[i].length == 2</code></li> <li><code>0 <= u_i, v_i < n</code></li> <li><code>u_i != v_i</code></li> <li>There are no duplicate edges.</li> <li>Each server can directly or indirectly reach another server.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	networkBecomesIdle(int[][] edges, int[] pat)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

networkBecomesIdle

public int networkBecomesIdle(int[][] edges,
 int[] pat)