Maximum Tea Deliveries with Minimum Distance
Learn this problem
GoogleFULLTIMEPHONE SCREENProblem statement
People and tea shops occupy integer coordinates on a one-dimensional line. Each shop can deliver one drink to at most one person, and each person can receive at most one drink. A delivery from a shop to a person is allowed only when their absolute distance is at most 5.
First maximize the number of deliveries. Among all matchings with that maximum count, minimize the sum of delivery distances. Return [maximumDeliveries, minimumTotalDistance] as a long[].
Function
optimizeTeaDeliveries(people: int[], shops: int[]) → long[]Examples
Example 1
people = [0,4,10]shops = [1,6,12]return = [3,5]Match 0-1, 4-6, and 10-12. All three people receive a drink and the total distance is 1 + 2 + 2 = 5.
Example 2
people = [0,1,20]shops = [2,30]return = [1,1]Only shop 2 can serve either of the first two people. Serving person 1 gives the same maximum count with the smaller distance 1.
Example 3
people = []shops = [0,5]return = [0,0]With no people, no delivery can be made and the minimum total distance is zero.
Constraints
0 <= people.length, shops.length <= 700-1000000000 <= people[i], shops[i] <= 1000000000- Coordinates may repeat and the input arrays need not be sorted.