FastPrep
Problem · Intervals

Minimum Retailers

● HardAmazonOA
See Amazon hiring insights

An online marketplace has onboarded n merchants, each operating within a designated geographical range. The operating zone of merchant i is defined by the interval spanning from zoneStart[i] to zoneEnd[i].

A set of k merchants is termed cohesive (inclusive) if there exists at least one merchant whose operational territory overlaps with (or touches) all the other (k-1) merchants’ operational zones.

The marketplace plans to relocate some merchants to new areas. Your goal is to determine the minimum number of merchants that need to be moved so that the remaining merchants form a cohesive subset.

Function Description

Complete the predefined function in the editor.

minimumRetailers has the following parameters:

  1. int zoneStart[n]: the left ends of the operating regions
  2. int zoneEnd[n]: the right ends of the operating regions

Returns

int: the smallest number of merchants that need to be relocated

Constraints

  • 1 ≤ n ≤ 10^5
  • 1 ≤ zoneStart[i] ≤ zoneEnd[i] ≤ 10^9 (1 <= i < n)
  • All regions have regions with the same start and end points.

Examples
01 · Example 1
zoneStart = [1, 3, 4, 6, 9]
zoneEnd = [2, 8, 5, 7, 10]
return = 2
Example 1 illustration
02 · Example 2
zoneStart = [1, 2, 3, 4]
zoneEnd = [2, 3, 5, 5]
return = 1
Region 1 (1, 2) intersects only region 2. (move regions 3 and 4) Region 2 (2, 3) intersects regions 1 and 3. (move region 4) Region 3 (3, 5) intersects regions 2 and 4. (move region 1) Region 4 (4, 5) intersects region 3. (move regions 1 and 2) The minimum number of moves is 1, moving region 1 or 4
03 · Example 3
zoneStart = [1, 2, 4]
zoneEnd = [7, 5, 6]
return = 0
Will update once find reliable resources. As always.
Constraints
  • 1 <= n <= 10^5
  • 1 <= regionStart[i] <= regionEnd[i] <= 10^9 (1 <= i <= n)
  • There can be multiple regions with the same start and end points
  • Complete constraints was added on 05-14-2025. You can find relevant source image will be uploaded next time..
    • More Amazon problems
    drafts saved locally
    public int minimumRetailers(int[] zoneStart, int[] zoneEnd) {
  // write your code here
}
    zoneStart[1, 3, 4, 6, 9]
    zoneEnd[2, 8, 5, 7, 10]
    expected2
    sign in to submit