Staff Alert Relay
A hospital has no group chat for urgent notices. Instead it uses a relay: when a person gets an alert, they pass it on to a fixed list of colleagues. Each hand-off takes a known number of minutes. The nurse might phone the porter in 2 minutes, while the porter takes 9 minutes to walk over to the lab. Hand-offs only go one way: the porter passing to the lab does not mean the lab passes back.
Everyone forwards the alert the moment it first reaches them, to everyone on their list at once. The safety officer wants to know how long it takes, from the moment one person gets it, until the very last person has it.
Your task
Write alertTime(n, handoffs, start). Staff are numbered 0 to n - 1. Each entry [from, to, minutes] in handoffs means that once from has the alert, to receives it from them minutes later. The alert begins with start at minute 0.
Return the minute at which the last person receives the alert. Each person counts from the earliest moment any hand-off reaches them. Return -1 if some person never receives it.
alertTime(n: int, handoffs: int[][], start: int) → int
Examples
n = 4 handoffs = [[0, 1, 2], [0, 2, 9], [1, 2, 3], [2, 3, 1]] start = 0
6
Person 1 has it at minute 2. Person 2 could get it straight from 0 at minute 9, but via 1 it arrives at 2 + 3 = 5. Person 3 gets it at 5 + 1 = 6. The last person is 3, at minute 6.
n = 3 handoffs = [[0, 1, 4], [2, 1, 1]] start = 0
-1
Person 1 gets it at minute 4, but nobody passes anything to person 2. Hand-offs only go one way, so [2, 1, 1] does not help. Return -1.
Constraints
- 1 ≤ n ≤ 1,000
- 0 ≤ handoffs.length ≤ 5,000
- 0 ≤ from, to < n and from ≠ to
- 0 ≤ minutes ≤ 100
- 0 ≤ start < n
- The same pair may appear more than once with different times
Start with brute force
Breadth-first search counts hops, not minutes, so it gives wrong answers here. A correct slow approach repeats this n - 1 times: go through every hand-off and see if it gives its target an earlier time. That is Bellman-Ford.
With 1,000 people and 5,000 hand-offs, that is about 5 million checks, and it ignores the useful fact that no hand-off takes negative time. Dijkstra uses that fact to settle each person once, for about 5,000 × log 5,000 ≈ 60,000 heap steps.
Hints
0 of 4 shown- Hint 1
In the first example, person 2 can be reached directly in 9 minutes or in two hops taking 5. What does that tell you about counting hops?
- Hint 2
Fewest hand-offs is not fastest. You need the earliest arrival time for each person, which is a shortest path where each edge has its own length.
- Hint 3
Of all the people who do not have a final time yet, which one can you be sure about right now? Think about the one with the smallest tentative time, when no minutes are negative.
- Hint 4
Use Dijkstra's algorithm. Keep a best-known time for each person (start = 0, others infinity) and a min-heap of (time, person). Pop the smallest; skip it if it is out of date; otherwise relax each hand-off from that person. The answer is the largest final time, or -1 if anyone is still at infinity.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Each person's arrival time is the length of the fastest route from start, where a route's length is the sum of its hand-off minutes. Dijkstra's algorithm finds all of these at once. Its key fact: among people without a final time, the one with the smallest tentative time is already final, because any other route to them has to pass through someone whose tentative time is at least as large, and minutes are never negative, so that route cannot arrive earlier.
Trace the first example from person 0. Tentative times start as 0: 0, everyone else ∞.
- Pop (0, person 0). Hand-offs give person 1 time 2 and person 2 time 9.
- Pop (2, person 1). Via 1, person 2 gets 2 + 3 = 5, better than 9. Update it and push (5, 2).
- Pop (5, person 2). Person 3 gets 5 + 1 = 6.
- Pop (6, person 3). No hand-offs.
- Pop (9, person 2). Its best is already 5, so this entry is out of date. Skip.
Final times: [0, 2, 5, 6]. The largest is 6.
JavaScript has no built-in heap, so the reference writes a small one. Python uses heapq. Rather than updating entries inside the heap, both push a fresh entry and skip stale ones when they come out, which is simpler and just as fast in practice.
function alertTime(n, handoffs, start) {
const out = Array.from({ length: n }, () => []);
for (const [from, to, minutes] of handoffs) out[from].push([to, minutes]);
const best = new Array(n).fill(Infinity);
best[start] = 0;
const heap = [[0, start]]; // min-heap of [time, person]
const push = (item) => {
heap.push(item);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p][0] <= heap[i][0]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = () => {
const top = heap[0], last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < heap.length && heap[l][0] < heap[m][0]) m = l;
if (r < heap.length && heap[r][0] < heap[m][0]) m = r;
if (m === i) break;
[heap[m], heap[i]] = [heap[i], heap[m]];
i = m;
}
}
return top;
};
while (heap.length > 0) {
const [time, person] = pop();
if (time > best[person]) continue; // an out-of-date entry
for (const [to, minutes] of out[person]) {
if (time + minutes < best[to]) {
best[to] = time + minutes;
push([best[to], to]);
}
}
}
const last = Math.max(...best);
return last === Infinity ? -1 : last;
}import heapq
def alert_time(n, handoffs, start):
out = [[] for _ in range(n)]
for frm, to, minutes in handoffs:
out[frm].append((to, minutes))
best = [float('inf')] * n
best[start] = 0
heap = [(0, start)] # min-heap of (time, person)
while heap:
time, person = heapq.heappop(heap)
if time > best[person]:
continue # an out-of-date entry
for to, minutes in out[person]:
if time + minutes < best[to]:
best[to] = time + minutes
heapq.heappush(heap, (best[to], to))
last = max(best)
return -1 if last == float('inf') else lastRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.