Merchant Capacity Interval Merge
DoorDash● MediumNEW GRADPHONE SCREENProblem statement
What the interview report shared
The interview report asked for intervals to be merged according to merchant. Each interval included capacity and time-limit information, and the output was categorized by merchant.
Task
Interval records are supplied through equal-length arrays. At index i, merchantIds[i], startTimes[i], endTimes[i], and capacities[i] describe a half-open interval [startTimes[i], endTimes[i]) with a fixed capacity.
For every pair of merchant and capacity, merge intervals that overlap or touch. Intervals with different merchants or different capacities never merge, and a merged interval retains its shared capacity.
Return one row [merchantId, startTime, endTime, capacity] for every merged interval. Sort the rows by merchant identifier, then start time, end time, and capacity, all in ascending order.
Function
mergeMerchantIntervals(merchantIds: int[], startTimes: int[], endTimes: int[], capacities: int[]) → int[][]Examples
Example 1
merchantIds = [7,7,7,8]startTimes = [1,4,3,0]endTimes = [4,6,5,2]capacities = [10,10,20,5]return = [[7,1,6,10],[7,3,5,20],[8,0,2,5]]The capacity-10 intervals for merchant 7 touch and become [1,6). Its capacity-20 interval stays separate. Merchant 8 forms its own category.
Example 2
merchantIds = [2,2,2]startTimes = [8,1,3]endTimes = [10,3,8]capacities = [4,4,4]return = [[2,1,10,4]]After ordering the records by time, all three capacity-4 intervals touch and merge into one interval.
Example 3
merchantIds = [3,1,3]startTimes = [5,2,1]endTimes = [7,4,2]capacities = [9,6,9]return = [[1,2,4,6],[3,1,2,9],[3,5,7,9]]Rows are categorized by merchant. The two merchant-3 intervals have the same capacity but remain separate because they neither overlap nor touch.
Constraints
0 <= merchantIds.length <= 100000startTimes.length,endTimes.length, andcapacities.lengthequalmerchantIds.length.1 <= merchantIds[i] <= 10^90 <= startTimes[i] < endTimes[i] <= 10^91 <= capacities[i] <= 10^9