AMAZON Coding Question – Solved

Amazon is working on optimizing its delivery zones to ensure efficient and timely delivery of packages. Each delivery zone is represented as an interval indicating the range of house numbers it covers. The delivery zones can overlap. Given is a list of n delivery zones, where the i-th zone covers the interval (a[i], b[i]) (inclusive). Additionally, given is a maximum allowed length, k, for any new delivery zone that can be added. Your task is to add exactly one new delivery zone (a, b) such that the length of this new zone (b - a) is less than or equal to k. The goal is to minimize the number of disconnected delivery zones after adding the new delivery zone. A set of delivery zones [ (a[1], b[1]), (a[2], b[2]), ..., (a[n], b[n])] is considered connected if every house number in the range (min(a[1], a[2], ..., a[n]), max(b[1], b[2], ..., b[n])) is covered by at least one of the delivery zones (a[i], b[i]) in the set. For an instance: - The set [(1, 2), (2, 3), (1, 5)] is connected because every house number in the interval (min(1, 2, 1), max(2, 3, 5)) = (1, 5) is covered by at least one of the delivery zones. - The set [(2, 2), (3, 4)] is not connected because the delivery zones (2, 2) and (3, 4) do not overlap each other and hence is disconnected. Note: The arrays 'a' and 'b' used above are considered to follow 1-based indexing. Example Consider the delivery zones: [(1, 5), (2, 4), (6, 6), (7, 14), (16, 19)] and k = 2. If you add a new delivery zone (5, 7) to the list, you can separate the zones into 2 connected sets: - [(1, 5), (2, 4), (5, 7), (6, 6), (7, 14)] - [(16, 19)] However, if you add a new delivery zone (14, 16), you will end up with 3 connected sets: - [(1, 5), (2, 4)] - [(6, 6)] - [(14, 16), (16, 19)]