Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

2039. The moment when the network is free

2039. The moment when the network is free, medium

I. Title Description:

At first glance today’s problem, a bit to be persuaded to retreat feeling!! Does XDM feel this way

But in order to improve our own ability, we still have the patience to read through the questions and find out the important information

Ii. Analysis of Ideas:

1. What ideas does this question examine? What’s your thinking?

So how do we do this problem, we can analyze it, what does it tell us that’s useful

  • The number of servers is from 0 to n-1, and 0 is the primary server. All other servers send messages to the primary server, and the primary server responds to the messages in the original way

  • Between nodes, all information can be sent in 1 second

  • Each server can communicate with each other through a certain path, but the title requires the minimum path, and there is at most one information line between servers, there will not be two or more information lines between two nodes

  • If the server receives a packet from primary server 0 within the specified time, the server does not resend the packet. If the server does not receive a packet from primary server 0 within the specified time, the server resends the packet

  • Finally, we need to calculate the earliest time when the network becomes idle, which means that every node in the network has to be idle. At this point, we calculate the last idle node, which is the earliest idle time of the entire network

    After all, the overall result is the result of the efforts of everyone in the team

So, according to the example in the question, we can analyze and deduce:

As an example, edges = [[0,1],[1,2]], patience = [0,2,1]

According to the figure above, we need to distinguish two cases, that is, the time of the node from sending packets to receiving packets is less than the timeout time p (2t <= P), then there will be no retransmission, the total time is 2t seconds, 2t + 1 seconds is idle

The packet is resended only when the time for sending the first packet to receiving the packet exceeds the timeout period p (2T > p). The total time is P * ((2T-1)/P) + 2T. Finally, P * ((2T-1)/P) + 2T + 1 second

So now that we know the math of how to calculate the last idle time of the network, we can look at the shortest path problem, right

Shortest path, detailed analysis will not be repeated, for the shortest path after the problem together to reason, temporarily we can understand, the first node and node connection relationship is expressed as follows:

Next, we can directly use the breadth-first algorithm BFS to calculate the shortest path

2. Try coding

Based on the above logic and analysis, we can translate it into the following code

The encoding is as follows:

func networkBecomesIdle(edges [][]int, p []int) (ans int) {
    n := len(p)
    g := make([] []int, n)
    // Find the connection between nodes, as in the case above
    //g[0] = [1] -- indicates that node 0 can connect to node 1
	//g[1] = [0,2] -- indicates 1 node, can connect 0 node, and 2 node
	//g[2] = [1] -- indicates 2 node, can connect 1 node
    for _, e := range edges {
        x, y := e[0], e[1]
        g[x] = append(g[x], y)
        g[y] = append(g[y], x)
    }

    vis := make([]bool, n)
    vis[0] = true
    q := []int{0}
    // Use BFS to calculate the shortest path
    for t := 1; q ! =nil; t++ {
        tmp := q
        q = nil
        for _, x := range tmp {
            for _, v := range g[x] {
                if vis[v] {
                    continue
                }
                vis[v] = true
                q = append(q, v)
                // Calculate the latest idle time
                ans = max(ans, (t*2- 1)/p[v] * p[v] + t*2 +1)}}}return
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}
Copy the code

From the above code, we know that the main logic is:

  • Find nodes and connections between nodes
  • The BFS breadth-first algorithm is used to calculate the shortest distance from the node to master node 0 and the latest idle time of the node
  • Finally, the latest idle time with the largest value is the earliest idle time of the entire network

Iv. Summary:

The earliest idle time of the entire network depends on the latest idle time of the node, and the timeout retransmission time needs to be handled properly

In this case, the time and space complexity is O(n+m).

Original address: 2039. The moment the network is idle

Today is here, learning, if there is a deviation, please correct

Welcome to like, follow and favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~