A company has n offices on a city's street grid; offices[i] is the list of whole-number coordinates of office i (usually [x, y]; some cities also count the floor, a third coordinate). Once a month every office sends one person to a meeting, and the meeting must be held in one of the offices. People travel along the streets, so the distance between two offices is the Manhattan distance: the sum of the absolute differences of their coordinates.
Write meeting_office(offices) that returns the index of the office with the smallest total travel distance from all offices (the host office contributes 0). If several offices tie, return the smallest index.
The tests use up to 50,000 offices, far too many to add up the distance for every pair of offices. They build their maps with office_map(n, seed, dims), which is available in your code.
Examples
Input: offices = [[0, 0], [10, 0], [2, 1], [3, 9], [1, 1]]
Output: 2
Explanation: the totals are 27, 45, 22, 47 and 23. Office 2 at [2, 1] needs the least travel.
Input: offices = [[5], [1], [9], [1]]
Output: 0
Explanation: on a single street the totals are 12, 12, 20 and 12. Offices 0, 1 and 3 tie,
and office 0 has the smallest index.
Constraints
1 <= n <= 50000; every office has the same number of coordinates, between 1 and 3- coordinates are whole numbers between
0and10**6; two offices may share a position
Goals
- Find the row of a dataset with the smallest total distance to all the others
- Use the fact that a Manhattan distance is a sum of separate one-feature distances
- Replace a comparison of every pair by sorting each feature once