The Time When the Network Becomes Idle
Problem
A network of n servers (node 0 is the master) is connected by bidirectional links, each taking one second to traverse. At second 0 every non-master server sends a message to the master. A server with patience patience[i] resends its message every patience[i] seconds until it receives the reply, which arrives a round-trip time after the message that triggered it. Return the earliest second when no more messages are travelling anywhere (the network becomes idle).
The round-trip time of server i is 2 · dist[i], where dist[i] is its shortest hop distance from the master — found with a single BFS. From that we compute, per server, when its last (needless) resend happens and when its final reply lands; the network is idle one second after the latest such reply.
edges = [[0,1],[1,2],[0,2]], patience = [0,2,1]4from collections import deque
def network_becomes_idle(edges, patience):
n = len(patience)
adj = {i: [] for i in range(n)}
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
dist = [-1] * n
dist[0] = 0
q = deque([0])
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)
ans = 0
for i in range(1, n):
rtt = 2 * dist[i]
last_send = (rtt - 1) // patience[i] * patience[i]
last_reply = last_send + rtt
ans = max(ans, last_reply + 1)
return ansfunction networkBecomesIdle(edges, patience) {
const n = patience.length;
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const dist = new Array(n).fill(-1);
dist[0] = 0;
const q = [0];
for (let h = 0; h < q.length; h++) {
const u = q[h];
for (const v of adj[u]) {
if (dist[v] === -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
let ans = 0;
for (let i = 1; i < n; i++) {
const rtt = 2 * dist[i];
const lastSend = Math.floor((rtt - 1) / patience[i]) * patience[i];
const lastReply = lastSend + rtt;
ans = Math.max(ans, lastReply + 1);
}
return ans;
}class Solution {
public int networkBecomesIdle(int[][] edges, int[] patience) {
int n = patience.length;
List<Integer>[] adj = new List[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
for (int[] e : edges) {
adj[e[0]].add(e[1]);
adj[e[1]].add(e[0]);
}
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[0] = 0;
Queue<Integer> q = new LinkedList<>();
q.offer(0);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.offer(v);
}
}
}
int ans = 0;
for (int i = 1; i < n; i++) {
int rtt = 2 * dist[i];
int lastSend = (rtt - 1) / patience[i] * patience[i];
int lastReply = lastSend + rtt;
ans = Math.max(ans, lastReply + 1);
}
return ans;
}
}class Solution {
public:
int networkBecomesIdle(vector<vector<int>>& edges, vector<int>& patience) {
int n = patience.size();
vector<vector<int>> adj(n);
for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
vector<int> dist(n, -1);
dist[0] = 0;
queue<int> q;
q.push(0);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
int ans = 0;
for (int i = 1; i < n; i++) {
int rtt = 2 * dist[i];
int lastSend = (rtt - 1) / patience[i] * patience[i];
int lastReply = lastSend + rtt;
ans = max(ans, lastReply + 1);
}
return ans;
}
};Explanation
Every link costs one second, so a server's message and its reply each take dist[i] seconds, for a round-trip time of 2·dist[i]. The first reply to server i therefore arrives at second 2·dist[i]. We get all the dist values in one BFS from the master node 0.
Before that reply comes back, the impatient server keeps resending every patience[i] seconds. The useful question is: what is the last moment it sends a (now-redundant) message that will still generate traffic? Its resends happen at 0, p, 2p, …; the last one strictly before the reply at 2·dist[i] is at second lastSend = ⌊(2·dist[i]−1)/p⌋ · p.
That last message's reply lands at lastSend + 2·dist[i]. After it arrives, server i is silent. The whole network goes idle one second after the latest such reply across all servers — hence the + 1 and the running maximum.
Node 0 is the master and never sends, so we skip it in the loop.
Worked example: both servers are 1 hop away (round-trip 2). Server 1 (patience 2) only sends once; its reply lands at 2. Server 2 (patience 1) resends at second 1, and that reply lands at 1 + 2 = 3. The latest reply is 3, so the network is idle at 3 + 1 = 4.