Minimum Retailers
Updated
Problem statement
An online marketplace has onboarded n retailers, each operating within a designated geographical range. Retailer i operates over the interval from regionStart[i] to regionEnd[i] (inclusive on both ends).
A set of k retailers is said to be inclusive if there exists at least one retailer in the set whose operating interval intersects (overlaps with, or touches at an endpoint) the interval of each of the other k - 1 retailers individually. In other words, some chosen retailer must pairwise intersect every other retailer in the set; the other retailers do not need to intersect one another.
The marketplace wants to relocate some retailers to a different location. A relocated retailer is removed from the remaining set (it no longer participates in forming the inclusive set). Determine the minimum number of retailers that must be relocated so that the remaining retailers form an inclusive set.
Equivalently, if you select one retailer i to act as the hub, every retained retailer's interval must intersect retailer i's interval, and all retailers whose intervals do not intersect retailer i's interval must be relocated. The answer is the minimum number of relocations over all possible choices of hub, i.e. n minus the maximum, over all i, of the number of intervals (including i itself) that intersect interval i.
Complete the function minimumRetailers in the editor below.
minimumRetailers has the following parameters:
int regionStart[n]: the left ends of the operating regionsint regionEnd[n]: the right ends of the operating regions
int: the minimum number of retailers to relocate
Function
minimumRetailers(zoneStart: int[], zoneEnd: int[]) → intExamples
Example 1
zoneStart = [1, 3, 4, 6, 9]zoneEnd = [2, 8, 5, 7, 10]return = 2Intervals: retailer 1 = [1, 2], retailer 2 = [3, 8], retailer 3 = [4, 5], retailer 4 = [6, 7], retailer 5 = [9, 10]. Choosing retailer 2 ([3, 8]) as the hub: it intersects retailer 3 ([4, 5]) and retailer 4 ([6, 7]), but not retailer 1 ([1, 2]) or retailer 5 ([9, 10]). So retailers 2, 3, 4 already form an inclusive set of size 3. Relocating retailers 1 and 5 leaves an inclusive set, requiring 2 relocations, which is the minimum.
Example 2
zoneStart = [1, 2, 3, 4]zoneEnd = [2, 3, 5, 5]return = 1Region 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
Example 3
zoneStart = [1, 2, 4]zoneEnd = [7, 5, 6]return = 0Intervals: retailer 1 = [1, 7], retailer 2 = [2, 5], retailer 3 = [4, 6]. Choosing retailer 1 ([1, 7]) as the hub: it intersects retailer 2 ([2, 5]) and retailer 3 ([4, 6]). All three retailers are retained with retailer 1 as the hub, so the set is already inclusive and no relocations are needed. The answer is 0.
Constraints
1 ≤ n ≤ 10^51 ≤ regionStart[i] ≤ regionEnd[i] ≤ 10^9(for eachi,0 ≤ i < n)- Multiple regions may share the same start and end points.
More Amazon interview questions
- Get Smallest Base SegmentOA · Seen Nov 2026
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Minimum Cost of Left and Right PropagationOA · Seen Nov 2026
- Minimum Grid InconvenienceOA · Seen Nov 2026
- 3SumPHONE SCREEN · Seen Nov 2026
- Circular Primes Below a LimitPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
- Maximize Shipment Order by Sorting One WindowOA · Seen Nov 2026
- Cheapest Flights Within K StopsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Calculate Minimum Satellites RequiredGoogle · OAGoogle interview questions
- Smallest Set Covering IntervalsSnowflake · OASnowflake interview questions
- Maximum Compatible Time WindowsIBM · OAIBM interview questions
- Task SchedulingJP Morgan Chase · OAJP Morgan Chase interview questions
- Minimum Markers to Clear Line SegmentsHSBC · OAHSBC interview questions
- Minimum Machines for TasksExpedia · OAExpedia interview questions
- Meeting RoomWeWork · OAWeWork interview questions
- Meetup Schedule 📆WeRide · OAWeRide interview questions
- Most Disjoint Intervals From Starts and DurationsDocuSign · OADocuSign interview questions
- University Career FairRoblox · OARoblox interview questions
Amazon interview experiences
- Amazon SWE OA with AI Coding: 1 Experience
- Amazon SWE Intern Phone Screen Interview Experience: 1 Experience
- Amazon New Grad SDE I OA and Virtual Onsite: 1 Experience
- Amazon BIE Intern SQL and Interview Questions: 17 Experiences
- Amazon Experienced SWE AI-Assisted Debugging OA: 1 Experience
- Amazon SDE II (L5) Interview Questions: 5 Experiences