Choose K pickup locations minimizing L1 distance

Coding: K Shuttle Pickup Locations (L1)

You are given the coordinates of N people on a 2D grid. You want to open K shuttle pickup locations (pickup points) so that the sum of Manhattan (L1) distances from each person to their nearest pickup location is minimized.

Input

• An integer N (number of people).
• An array points of length N, where points[i] = (xi, yi) are integer coordinates.
• An integer K (number of pickup locations).

Output

• Return the minimum possible total L1 distance:

$\sum_{i=1}^{N} \min_{j=1..K} (|x_i - X_j| + |y_i - Y_j|)$

where $(X_j, Y_j)$ are the chosen pickup locations.

Clarifications / assumptions (state in your solution)

• Are pickup locations required to be at integer coordinates?
• Are pickup locations required to be chosen from existing people’s coordinates, or can they be anywhere?

Constraints (you may assume)

Provide an algorithm appropriate for interview constraints (e.g., N up to a few thousand, K up to N).

Choose K Pickup Locations Minimizing L1 Distance

You are given the coordinates of N people on a 2D grid and an integer K. Open K shuttle pickup locations so that the sum of Manhattan (L1) distances from each person to their nearest pickup location is minimized, and return that minimum total distance.

For this executable version, adopt the standard facility-location simplification (state your assumptions in an interview): each pickup location must be placed at one of the given people's coordinates. Two people may share the same coordinate, and a pickup location may coincide with multiple people. If K >= N, every person can host (or share) a pickup point, so the total distance is 0.

Function signature: chooseKLocations(points, k) returns an integer — the minimum achievable total L1 distance.

Definitions

For person i at (xi, yi) and the chosen set of centers C, their cost is min over (X, Y) in C of (|xi - X| + |yi - Y|). The answer is the sum of these costs over all people, minimized over all valid choices of C with |C| = K.

Examples

• points = [[0,0],[0,1],[10,10],[10,11]], k = 2 -> 2 (centers at (0,0) and (10,10); the two remaining people are each 1 away).
• points = [[0,0],[2,0],[4,0]], k = 1 -> 4 (center at the median (2,0); costs 2 + 0 + 2).
• points = [[0,0],[3,4]], k = 2 -> 0 (each person hosts a pickup point).

Note on approach

General K-medians is NP-hard, but with the centers-must-be-people restriction and small interview-sized inputs you can return the exact optimum by enumerating every K-subset of points and scoring each in O(N) — overall O(C(N,K) * N * K). State this complexity and, in a real interview, also discuss heuristics (k-means/k-medians style local search, or DP for the 1D case) for larger inputs.

Hints

1. Clarify the rules first: must centers be integer coordinates, and must they be chosen from existing people? Here we assume centers must be one of the given points -- a standard facility-location simplification that makes an exact answer tractable.
2. If K >= N, you can give every person their own pickup point, so the total distance is 0. Handle this special case up front.
3. For each candidate set of K centers, the cost of a person is the L1 distance to their NEAREST center -- not to all of them. Take the min over centers, then sum over people.
4. With centers restricted to the given points and small N, enumerate every K-subset of points (itertools.combinations) and keep the best total. This is exact.
5. For larger inputs, discuss heuristics: k-medians local search (Lloyd-style swap), or note that the 1D version decomposes (sort + DP) while the 2D L1 version couples x and y through the assignment.