Leetcode 2039: The Time When the Network Becomes Idle
You are managing a network of servers connected by communication channels. One server, labeled as 0, acts as the master server, while the others are data servers. Each data server sends a message to the master server at the start and waits for a reply. The reply travels back via the same route the message took. If a server does not receive a reply within a specific period (defined by its patience value), it resends the message. The goal is to determine when the network will become idle, meaning there are no active messages being transmitted or received.
Problem
Approach
Steps
Complexity
Input: The network is represented by edges and patience values for each server.
Example: edges = [[0,1],[1,2]], patience = [0,3,2]
Constraints:
• n == patience.length
• 2 <= n <= 10^5
• patience[0] == 0
• 1 <= patience[i] <= 10^5 for 1 <= i < n
• 1 <= edges.length <= min(10^5, n * (n - 1) / 2)
• edges[i].length == 2
• 0 <= ui, vi < n
• ui != vi
• No duplicate edges exist, and all servers are connected.
Output: The function returns the earliest time (in seconds) when the network becomes idle.
Example: Output: 7
Constraints:
• The returned time is a positive integer.
Goal: Calculate the time at which the last reply is received, accounting for resending rules based on patience values.
Steps:
• Construct a graph representation of the network using the edges.
• Perform a Breadth-First Search (BFS) to compute the shortest distance from the master server (0) to all other servers.
• For each server, calculate the round-trip time for its messages.
• Determine the last time a server resends its message before the network becomes idle.
• Find the maximum time across all servers and return it as the result.
Goal: The problem constraints define the size and properties of the input.
Steps:
• All servers are directly or indirectly connected.
• The patience value for the master server is always 0.
Assumptions:
• Messages travel optimally between servers using the shortest path.
• Replies are sent instantly upon reaching the master server.
• Servers only resend messages if they do not receive a reply within their patience interval.
• Input: edges = [[0,1],[1,2]], patience = [0,3,2]
• Explanation: Server 1 sends its message and receives a reply by second 2, so no resends occur. Server 2 resends its message once before receiving a reply by second 4. The network becomes idle at second 7.
• Input: edges = [[0,1],[0,2],[1,2]], patience = [0,5,5]
• Explanation: Both servers 1 and 2 receive replies by second 2. No resends occur, and the network becomes idle at second 3.
Approach: The solution uses BFS to compute shortest distances, followed by calculations of resending times and idle times for each server.
Observations:
• Shortest distance is crucial for determining the timing of replies.
• Servers with higher patience values may not resend messages often, reducing overall activity in the network.
• Using a BFS ensures efficient computation of shortest distances for all servers.
• Patience values affect the timing of last resends, which determines the idle time.
Steps:
• Parse the input to construct the network graph.
• Perform a BFS starting from the master server to compute the shortest distance for each server.
• Calculate the round-trip time for each server's messages.
• For each server, determine the last resend time based on its patience value.
• Return the maximum time among all servers plus one as the idle time.
Empty Inputs:
• None, as input is guaranteed to have at least two servers.
Large Inputs:
• A fully connected network with maximum n = 10^5 servers.
Special Values:
• All servers except the master server have the same patience value.
• Servers are connected in a straight line.
Constraints:
• No duplicate edges and all servers are connected.
int networkBecomesIdle(vector<vector<int>>& edges, vector<int>& patience) {
int n = patience.size();
vector<vector<int>> grid(n);
for(auto e: edges) {
grid[e[0]].push_back(e[1]);
grid[e[1]].push_back(e[0]);
}
vector<int> sd(n, INT_MAX); // shortest distance(sd) to master;
sd[0] = 0;
queue<int> q;
vector<int> vis(n, 0);
q.push(0);
vis[0] = 1;
int t = 0;
while(!q.empty()) {
int sz = q.size();
t++;
while(sz--) {
int node = q.front();
q.pop();
for(auto it: grid[node]) {
if(vis[it]) continue;
vis[it] = true;
sd[it] = t;
q.push(it);
}
}
}
int mx = 0;
for(int i = 0; i < n; i++) {
int dist = 2 * sd[i];
int pat = patience[i];
if(pat >= dist) {
mx = max(mx, dist);
} else {
int mod = dist % pat == 0? pat: dist % pat;
mx = max(mx, dist - mod + dist);
}
}
return mx + 1;
}
1 : Function Definition
int networkBecomesIdle(vector<vector<int>>& edges, vector<int>& patience) {
The function `networkBecomesIdle` takes two arguments: a list of edges representing the network and a list `patience` containing the patience level of each node. It returns the time when the entire network becomes idle.
2 : Variable Initialization
int n = patience.size();
The variable `n` stores the number of nodes in the network, determined by the size of the `patience` array.
3 : Grid Initialization
vector<vector<int>> grid(n);
The `grid` variable is initialized as a 2D vector to represent the network as an adjacency list, where each node points to its connected nodes.
4 : Building Adjacency List
for(auto e: edges) {
This loop iterates over all edges in the network and constructs the adjacency list for each node by adding the connected nodes.
5 : Adjacency List Population
grid[e[0]].push_back(e[1]);
For each edge, the nodes are bidirectionally connected, so this line adds the destination node to the source node’s adjacency list.
6 : Adjacency List Population
grid[e[1]].push_back(e[0]);
Similarly, the destination node adds the source node to its adjacency list, completing the bidirectional connection.
7 : Distance Initialization
vector<int> sd(n, INT_MAX); // shortest distance(sd) to master;
The `sd` vector is initialized to store the shortest distance from the master node (node 0) to all other nodes, initially set to `INT_MAX` (infinity).
8 : Distance Initialization
sd[0] = 0;
The distance to the master node (node 0) is set to 0, as the master node is the starting point.
9 : Queue Initialization
queue<int> q;
A queue `q` is initialized for Breadth-First Search (BFS) to traverse the network.
10 : Visited Initialization
vector<int> vis(n, 0);
The `vis` vector is initialized to keep track of visited nodes during the BFS traversal.
11 : Queue Push
q.push(0);
The master node (node 0) is pushed into the queue to start the BFS traversal.
12 : Visited Update
vis[0] = 1;
The master node is marked as visited.
13 : Time Initialization
int t = 0;
The variable `t` tracks the time it takes for each node to receive a message during the BFS traversal.
14 : BFS Loop
while(!q.empty()) {
This `while` loop runs as long as there are nodes in the queue, performing the BFS to compute shortest distances.
15 : Queue Size
int sz = q.size();
The variable `sz` stores the number of nodes in the current level of the BFS.
16 : Time Increment
t++;
The time `t` is incremented as we move to the next level of the BFS.
17 : BFS Inner Loop
while(sz--) {
This inner loop iterates over each node in the current BFS level.
18 : Node Processing
int node = q.front();
The current node is retrieved from the front of the queue for processing.
19 : Queue Pop
q.pop();
The current node is removed from the queue.
20 : Neighbor Traversal
for(auto it: grid[node]) {
This loop iterates over all the neighbors of the current node.
21 : Visited Check
if(vis[it]) continue;
If a neighbor has already been visited, we skip it.
22 : Visited Update
vis[it] = true;
The neighbor is marked as visited.
23 : Distance Update
sd[it] = t;
The shortest distance to the neighbor is updated to the current time `t`.
24 : Queue Push
q.push(it);
The neighbor is added to the queue for further processing.
25 : Max Time Calculation
int mx = 0;
The variable `mx` will store the maximum time required for the last node to become idle.
26 : Time Calculation Loop
for(int i = 0; i < n; i++) {
This loop calculates the time for each node to become idle.
27 : Distance to Time Calculation
int dist = 2 * sd[i];
The time is calculated as twice the shortest distance because the message has to travel back and forth.
28 : Patience Check
int pat = patience[i];
The patience of each node is retrieved to determine how long they will wait for a message before becoming idle.
29 : Patience Check Logic
if(pat >= dist) {
If the node’s patience is greater than or equal to the distance, it will become idle after the message travels back and forth.
30 : Max Time Update
mx = max(mx, dist);
The maximum time is updated if this node’s time is greater than the previous maximum.
31 : Patience Check Else
} else {
If the node’s patience is less than the time required, it will become idle earlier.
32 : Mod Time Calculation
int mod = dist % pat == 0? pat: dist % pat;
The time calculation is adjusted based on the node’s patience and the message travel time.
33 : Max Time Update
mx = max(mx, dist - mod + dist);
The maximum time is updated based on the adjusted time calculation.
34 : Return Statement
return mx + 1;
The function returns the maximum time `mx` plus 1 to account for the last time unit.
Best Case: O(n + m), where n is the number of servers and m is the number of edges.
Average Case: O(n + m)
Worst Case: O(n + m)
Description: BFS traversal and idle time calculation are linear in terms of servers and edges.
Best Case: O(n + m)
Worst Case: O(n + m)
Description: Graph representation and BFS queue storage dominate space usage.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus