Skip to content

Commit 3d2b268

Browse files
fishercoder1534fishercoder1534
committed
add 2039
1 parent a3b9465 commit 3d2b268

File tree

3 files changed

+129
-0
lines changed

3 files changed

+129
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ ★
88

99
| # | Title | Solutions | Video | Difficulty | Tag
1010
|-----|----------------|---------------|--------|-------------|-------------
11+
|2039|[The Time When the Network Becomes Idle](https://leetcode.com/problems/the-time-when-the-network-becomes-idle/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2039.java) ||Medium||
1112
|2034|[Stock Price Fluctuation](https://leetcode.com/problems/stock-price-fluctuation/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2034.java) ||Medium||
1213
|2033|[Minimum Operations to Make a Uni-Value Grid](https://leetcode.com/problems/minimum-operations-to-make-a-uni-value-grid/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2033.java) ||Medium||
1314
|2032|[Two Out of Three](https://leetcode.com/problems/two-out-of-three/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2032.java) ||Easy||

‎src/main/java/com/fishercoder/solutions/_2039.java

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.Arrays;
4+
import java.util.HashMap;
5+
import java.util.HashSet;
6+
import java.util.LinkedList;
7+
import java.util.Map;
8+
import java.util.Queue;
9+
import java.util.Set;
10+
11+
public class _2039 {
12+
public static class Solution1 {
13+
public int networkBecomesIdle(int[][] edges, int[] patience) {
14+
int n = patience.length;
15+
int[] distances = findShortestPathToMasterServer(edges, n);
16+
int seconds = 0;
17+
for (int i = 1; i < n; i++) {
18+
int roundTripTime = distances[i] * 2;
19+
int numberOfMessages = roundTripTime / patience[i];
20+
int lastMessageArriveTime = roundTripTime;
21+
if (roundTripTime > patience[i]) {
22+
lastMessageArriveTime += patience[i] * (roundTripTime % patience[i] == 0 ? (numberOfMessages - 1) : numberOfMessages);
23+
}
24+
seconds = Math.max(seconds, lastMessageArriveTime);
25+
}
26+
return seconds + 1;
27+
}
28+
29+
private int[] findShortestPathToMasterServer(int[][] edges, int n) {
30+
int[] distances = new int[n];
31+
Arrays.fill(distances, n);
32+
Queue<Integer> queue = new LinkedList<>();
33+
Map<Integer, Set<Integer>> neighborsMap = new HashMap<>();
34+
for (int[] edge : edges) {
35+
if (edge[0] == 0) {
36+
queue.offer(edge[1]);
37+
}
38+
if (edge[1] == 0) {
39+
queue.offer(edge[0]);
40+
}
41+
Set<Integer> set1 = neighborsMap.getOrDefault(edge[0], new HashSet<>());
42+
set1.add(edge[1]);
43+
neighborsMap.put(edge[0], set1);
44+
Set<Integer> set2 = neighborsMap.getOrDefault(edge[1], new HashSet<>());
45+
set2.add(edge[0]);
46+
neighborsMap.put(edge[1], set2);
47+
}
48+
int distance = 1;
49+
boolean[] visited = new boolean[n];
50+
visited[0] = true;
51+
while (!queue.isEmpty()) {
52+
int size = queue.size();
53+
for (int i = 0; i < size; i++) {
54+
Integer curr = queue.poll();
55+
if (visited[curr]) {
56+
continue;
57+
}
58+
visited[curr] = true;
59+
distances[curr] = Math.min(distance, distances[curr]);
60+
Set<Integer> neighbors = neighborsMap.getOrDefault(curr, new HashSet<>());
61+
for (int neighbor : neighbors) {
62+
if (!visited[neighbor]) {
63+
queue.offer(neighbor);
64+
}
65+
}
66+
}
67+
distance++;
68+
}
69+
return distances;
70+
}
71+
}
72+
}

‎src/test/java/com/fishercoder/_2039Test.java

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.utils.CommonUtils;
4+
import com.fishercoder.solutions._2039;
5+
import org.junit.BeforeClass;
6+
import org.junit.Test;
7+
8+
import static org.junit.Assert.assertEquals;
9+
10+
public class _2039Test {
11+
private static _2039.Solution1 solution1;
12+
private static int[][] edges;
13+
private static int[] patience;
14+
15+
@BeforeClass
16+
public static void setup() {
17+
solution1 = new _2039.Solution1();
18+
}
19+
20+
@Test
21+
public void test1() {
22+
edges = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,1],[1,2]");
23+
patience = new int[]{0, 2, 1};
24+
assertEquals(8, solution1.networkBecomesIdle(edges, patience));
25+
}
26+
27+
@Test
28+
public void test2() {
29+
edges = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,1],[0,2],[1,2]");
30+
patience = new int[]{0, 10, 10};
31+
assertEquals(3, solution1.networkBecomesIdle(edges, patience));
32+
}
33+
34+
@Test
35+
public void test3() {
36+
edges = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("" +
37+
"[3,8],[4,13],[0,7],[0,4],[1,8],[14,1],[7,2],[13,10],[9,11],[12,14],[0,6],[2,12],[11,5],[6,9],[10,3]");
38+
patience = new int[]{0, 3, 2, 1, 5, 1, 5, 5, 3, 1, 2, 2, 2, 2, 1};
39+
assertEquals(20, solution1.networkBecomesIdle(edges, patience));
40+
}
41+
42+
@Test
43+
public void test4() {
44+
edges = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,1],[1,2]");
45+
patience = new int[]{0, 2, 2};
46+
assertEquals(7, solution1.networkBecomesIdle(edges, patience));
47+
}
48+
49+
@Test
50+
public void test5() {
51+
edges = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,1],[1,2]");
52+
patience = new int[]{0, 2, 3};
53+
assertEquals(8, solution1.networkBecomesIdle(edges, patience));
54+
}
55+
56+
}

0 commit comments

Comments
 (0)