FastPrep
Problem · Sorting

Minimum Weighted Manhattan Travel Cost

Learn this problem
● MediumConcentric AI logoConcentric AIFULLTIMEOA

Problem statement

You are given three equal-length arrays x, y, and people. Location i is the integer coordinate (x[i], y[i]) and contains people[i] people.

Choose any integer meeting coordinate (meetingX, meetingY). Its total travel cost is:

sum(people[i] * (abs(meetingX - x[i]) + abs(meetingY - y[i]))).

Return the minimum possible total travel cost. If several coordinates are optimal, only the minimum cost matters.

Function

minWeightedTravelCost(x: int[], y: int[], people: int[]) → long

Examples

Example 1

x = [0,4]y = [0,0]people = [1,1]return = 4

Any meeting x-coordinate from 0 through 4 with y-coordinate 0 has total cost 4.

Example 2

x = [0,10,20]y = [0,0,10]people = [1,3,1]return = 30

The weighted medians are meetingX = 10 and meetingY = 0. The three weighted costs are 10, 0, and 20.

Example 3

x = [-2,3]y = [5,-1]people = [4,1]return = 11

The higher-weight first location is an optimal meeting coordinate. The second group travels 5 horizontal and 6 vertical units.

Constraints

  • 1 <= x.length == y.length == people.length <= 100000
  • -1000000 <= x[i], y[i] <= 1000000
  • 1 <= people[i]
  • sum(people) <= 1000000000
  • The answer fits in a signed 64-bit integer.

More Concentric AI problems

drafts saved locally
public long minWeightedTravelCost(int[] x, int[] y, int[] people) {
    // Write your code here.
}
x[0,4]
y[0,0]
people[1,1]
expected4
checking account