A company has offices numbered 0 to offices - 1. Each link [a, b, minutes] means office a can pass news to office b, taking minutes (always 0 or more). Links only work in the stated direction. News starts at office start at minute 0, and every office forwards it as soon as it arrives.
Write a function that returns how many minutes it takes until every office has the news, or -1 if some office never gets it.
Going through office 2 (1 + 2 = 3 minutes) beats the direct 4-minute link.
In the first example, news reaches office 2 at minute 1, then office 1 at minute 3 through office 2, which beats the direct 4-minute link.
Write time_to_reach_all(offices, links, start) in Python or timeToReachAll(offices, links, start) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 22 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
What's being asked
Each office hears the news at the earliest time along any path from start. The answer is the latest of those earliest times. So you need the shortest path from start to every office.
Step 2
Why not BFS?
BFS counts edges, but here edges have different costs: one slow link can be worse than two fast ones. With non-negative costs, use Dijkstra's algorithm.
Step 3
Always settle the closest office next
Keep a min-heap of (time, office), starting with (0, start). Pop the smallest time. If that office already has a final time, skip it (it's an outdated entry). Otherwise its time is final, because every other route would have to go through somewhere at least as far. Push (time + minutes, next) for each of its links.
Step by step1 / 3
Office 0 hears at minute 0. Push its links: office 1 at 4, office 2 at 1.
Step 4
Finish up
When the heap is empty, if any office never got a final time, return -1. Otherwise return the largest final time.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Build an adjacency list. Run Dijkstra from start with a min-heap, recording each office's time the first time it's popped and skipping later, larger entries for it. If fewer than offices offices were reached, return -1; else return the maximum recorded time.
python
1import heapq
2
3
4def time_to_reach_all(offices, links, start):
5 graph = [[] for _ in range(offices)]
6 for a, b, minutes in links:
7 graph[a].append((b, minutes))
8 heard_at = {}
9 heap = [(0, start)]
↑(time, office), smallest time first
10 while heap:
11 time, office = heapq.heappop(heap)
12 if office in heard_at:
↑already settled with an earlier time
13 continue # already settled with an earlier time
14 heard_at[office] = time
↑first time popped = final time
15 for nxt, minutes in graph[office]:
16 if nxt not in heard_at:
17 heapq.heappush(heap, (time + minutes, nxt))
18 return max(heard_at.values()) if len(heard_at) == offices else -1
↑everyone reached? the latest one
javascript
1// JavaScript has no built-in heap, so here is a small binary min-heap of [time, office] pairs
2class MinHeap {
3 constructor() { this.items = [] }
4 get size() { return this.items.length }
5 push(item) {
6 const a = this.items
7 a.push(item)
8 let i = a.length - 1
9 while (i > 0) {
10 const parent = (i - 1) >> 1
11 if (a[parent][0] <= a[i][0]) break;
12 [a[parent], a[i]] = [a[i], a[parent]]
13 i = parent
14 }
15 }
16 pop() {
17 const a = this.items
18 const top = a[0]
19 const last = a.pop()
20 if (a.length) {
21 a[0] = last
22 let i = 0
23 for (;;) {
24 const l = 2 * i + 1
25 const r = l + 1
26 let smallest = i
27 if (l < a.length && a[l][0] < a[smallest][0]) smallest = l
28 if (r < a.length && a[r][0] < a[smallest][0]) smallest = r