FastPrepFastPrep
Problem Brief

Minimum Connected Delivery Zones After Adding One Interval

NEW GRADOA
See Amazon online assessment and hiring insights

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 delivery zones (a[i], b[i]) in the set.

For example:

  • [(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 a least one of the delivery zones.

    • Note ~~ Not sure about the operator inbetween (min(1, 2, 1), max(2, 3, 5)) and (1, 5). Following is the original source image. If you know about it, feel free to lmk. I am more than happy to modyify it. Many thanks in advance!

  • 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.

    • Amazon has something to say -

    The arrays 'a' and 'b' used above are considered to follow 1-based indexing!

    Function Description

    Write a function minimumSets.

    The function has the following parameters:

    1. 1. List a: an array of integers representing the start of each delivery zone
    2. 2. List b: an array of integers representing the end of each delivery zone
    3. 3. k: the maximum allowed length for the new delivery zone

    Returns

    int: the minimum number of connected delivery zone groups after optimally inserting one new delivery zone of length ≤ k.

    The problem statement was modified on 05-27-2025 to align with the original problem source found by an old friend. 🧡🙏 Related source ss was included in the Problem Source section below.

    1Example 1

    Input
    a = [1, 2, 6, 7, 16], b = [5, 4, 6, 14, 19], k = 2
    Output
    2
    Explanation
    The current delivery zones are: (1, 5), (2, 4), (6, 6), (7, 14), (16, 19) Add a new delivery zone (5, 7) (length = 2 ≤ k), which bridges the gap between (1, 5) and (6, 6), forming a larger connected component. Resulting components: Component 1: (1, 5), (2, 4), (5, 7), (6, 6), (7, 14) Component 2: (16, 19) ✅ Output: 2 However, if you add a new delivery zone (14, 16), you will end up with 3 connected sets: (1,5),(2.4),(5,7) (6,6) (7.14), (14, 16), (16, 19) Therefore, the optimal solution is to add the delivery zone (5, 7), resulting in the minimum number of connected sets, which is 2.

    2Example 2

    Input
    a = [1, 2, 5, 10], b = [2, 4, 8, 11], k = 2
    Output
    2
    Explanation
    Initial intervals: (1, 2), (2, 4), (5, 8), (10, 11) Add a new delivery zone (4, 5) into the array since 5 - 4 <= 2. After that , there are 2 connected intervals - 1: (1, 2), (2, 4), (4, 5), (5, 8) 2: (10, 11) This test case was modified on 05-31-2025 to align with the original problem source found by an old friend. Endless thanks!

    Constraints

    Limits and guarantees your solution can rely on.

    • 1 <= n <= 10^5
    • 1 <= a[i] <= b[i] <= 10^9
    • 1 <= k <= 10^9
    public int minDisconnectedSets(int[] a, int[] b, int k) {
  // write your code here
}
    Input

    a

    [1, 2, 6, 7, 16]

    b

    [5, 4, 6, 14, 19]

    k

    2

    Output

    2

    Sign in to submit your solution.