Minimize Total Manhattan Distance to a Meeting Point

Problem: Given an array of [x, y] coordinates (points) and an array giving the number of people at each point, the cost to move everyone at a point (x,y) to a target point (a,b) is |x-a| + |y-b| per person. Find a target point such that the total cost to move every person to that point is minimized, and return that minimum total cost.

Constraints: Number of points < 10^5.

Approach: Because Manhattan distance decomposes into independent x and y components, the problem separates: the optimal target x-coordinate is the weighted median of all x-coordinates (weighted by the number of people at each point), and independently the optimal target y-coordinate is the weighted median of all y-coordinates. Sort points by x (and separately by y) weighted by population and find the weighted median in each dimension, then sum the weighted absolute differences. O(n log n).