FastPrep
Problem · Intervals

Minimum Connected Delivery Zones After Adding One Interval

Learn this problem
● HardAmazonNEW GRADOA
See Amazon hiring insights

Problem statement

Amazon is optimizing delivery zones. Each existing delivery zone is an inclusive interval [a[i], b[i]] on a continuous number line, and zones may overlap.

You are given arrays a and b of length n, and an integer k. You must add exactly one new delivery zone [x, y], where x and y are integers, x <= y, and y - x <= k.

After adding the new zone, merge intervals that overlap or share an endpoint. A connected delivery-zone group is one merged component. If one interval ends at 5 and another starts at 6, they are still disconnected because the open gap between 5 and 6 is uncovered on the continuous number line.

Return the minimum possible number of connected groups after choosing the new zone optimally.

For example, intervals [1, 2], [2, 3], and [1, 5] form one connected group because they overlap or touch and their union covers every point from 1 through 5. Intervals [2, 2] and [3, 4] are disconnected because the gap between 2 and 3 is uncovered.

Function

minDisconnectedSets(a: int[], b: int[], k: int) → int

Examples

Example 1

a = [1, 2, 6, 7, 16]b = [5, 4, 6, 14, 19]k = 2return = 2

The current zones are [1,5], [2,4], [6,6], [7,14], and [16,19]. Initially these form four groups: [1,5], [6,6], [7,14], and [16,19], because gaps such as (5,6) and (6,7) are uncovered.

Add the new zone [5,7], whose length is 7 - 5 = 2. This connects [1,5], [6,6], and [7,14] into one group. The interval [16,19] remains separate, so there are 2 connected groups.

Adding [14,16] would connect [7,14] and [16,19], but it would not connect the gaps between [1,5], [6,6], and [7,14], so it still leaves more than 2 groups. Therefore 2 is optimal.

Example 2

a = [1, 2, 5, 10]b = [2, 4, 8, 11]k = 2return = 2

The current zones are [1,2], [2,4], [5,8], and [10,11]. Add the new zone [4,5], whose length is 1 <= k. This connects [1,2], [2,4], [4,5], and [5,8] into one group. The zone [10,11] remains separate, so there are 2 connected groups.

Constraints

  • 1 <= n <= 105
  • a.length == b.length == n
  • 1 <= a[i] <= b[i] <= 109
  • 1 <= k <= 109

More Amazon problems

drafts saved locally
public int minDisconnectedSets(int[] a, int[] b, int k) {
  // write your code here
}
a[1, 2, 6, 7, 16]
b[5, 4, 6, 14, 19]
k2
expected2
checking account