Ambulance Service — Longest Driving Time - Deutsche Bank Online Assessment IIT BHU

Problem Preview

"In the city there are **N districts** (numbered from `0` to `N-1`) connected with **M streets**. The connections are described by two arrays, `A` and `B`, both of length `M`. A pair `(A[K], B[K])` marks a street between districts `A[K]` and `B[K]` (for `K` from `0` to `M-1`). There are also **L hospitals** whose locations are described by an array `H`. The `J`-th hospital is placed in district `H[J]` (for `J` from `0` to `L-1`). If an ambulance is needed in a district, one is sent from the hospital from which it will arrive in the **shortest time**. The ambulance arrives by the shortest possible route; passing one street takes it exactly **1 minute**. Potentially, there might be a patient in need in **any district of the city**. What is the **longest time required** to reach any possible patient with an ambulance? ## Function Write a function: ```cpp int solution(int N, vector<int> &A, vector<int> &B, vector<int> &H); ``` that, given an integer `N`, arrays `A` and `B` describing streets in the city, and an array `H` giving the locations of hospitals, returns an integer — the **longest driving time (in minutes) between a district and its closest hospital**. If some district **cannot be reached with an ambulance**, the function should return `-1`. --- # Examples ## Example 1 Given: ```text N = 6 A = [0, 1, 1, 3, 0] B = [1, 2, 3, 4, 5] H = [2, 4] ``` Your function should return **3**. District `5` has the longest waiting time. ### Graph ```text 2 🏥 | 1 / \ 0 3 | | 5 4 🏥 ``` **Edges:** ```text 0 — 1 1 — 2 1 — 3 3 — 4 0 — 5 ``` **Hospitals:** `2, 4` Distances to the nearest hospital: ```text District 0 → 2 District 1 → 1 District 2 → 0 District 3 → 1 District 4 → 0 District 5 → 3 ``` Therefore: ```text Answer = 3 ``` --- ## Example 2 Given: ```text N = 6 A = [0, 1, 1, 3, 0, 4] B = [1, 2, 3, 4, 5, 5] H = [2, 4] ``` Your function should return **2**. The district with the longest ambulance arrival time is district `0`. Every other district can be reached by an ambulance in at most `1` minute. ### Graph ```text 2 🏥 | 1 / \ 0 3 | | 5 — 4 🏥 ``` More precisely, the edges are: ```text 0 — 1 1 — 2 1 — 3 3 — 4 0 — 5 4 — 5 ``` **Hospitals:** `2, 4` Distances to the nearest hospital: ```text District 0 → 2 District 1 → 1 District 2 → 0 District 3 → 1 District 4 → 0 District 5 → 1 ``` Therefore: ```text Answer = 2 ``` --- ## Example 3 Given: ```text N = 6 A = [0, 1, 1, 3] B = [1, 2, 3, 4] H = [2, 4] ``` Your function should return **-1**. District `5` is not connected with any district with a hospital. ### Graph ```text 2 🏥 | 1 / \ 0 3 | 4 🏥 5 (isolated) ``` **Edges:** ```text 0 — 1 1 — 2 1 — 3 3 — 4 ``` District `5` has no connection to any hospital. Therefore: ```text Answer = -1 ``` --- ## Example 4 Given: ```text N = 3 A = [1] B = [2] H = [0, 1, 2] ``` Your function should return **0**. There is a hospital in every district. ### Graph ```text 0 🏥 1 🏥 — 2 🏥 ``` Since every district already contains a hospital: ```text District 0 → 0 District 1 → 0 District 2 → 0 ``` Therefore: ```text Answer = 0 ``` --- # Constraints Write an efficient algorithm for the following assumptions: * `N` is an integer within the range `[1..100,000]`; * `M` is an integer within the range `[0..100,000]`; * `L` is an integer within the range `[1..N]`; * the elements of `H` are all distinct; * each element of arrays `A`, `B` and `H` is an integer within the range `[0..N-1]`; * every street goes between two different districts; * there are no multiple streets between two districts."