Lintcode 1160 · Campus Bikes (三元组排序好题)

1160 · Campus Bikes
Algorithms
Medium

Description
On a campus represented as a 2D grid, there are
N≤M. Each worker and bike is a 2D coordinate on this grid.

Our goal is to assign a bike to each worker. Among the available bikes and workers, we choose the (worker, bike) pair with the shortest Manhattan distance between each other, and assign the bike to that worker. (If there are multiple (worker, bike) pairs with the same shortest Manhattan distance, we choose the pair with the smallest worker index; if there are multiple ways to do that, we choose the pair with the smallest bike index). We repeat this process until there are no available workers.

The Manhattan distance between two points
…
0≤workers[i][j],bikes[i][j]<1000
All worker and bike locations are distinct.
1≤workers.length≤bikes.length≤1000

Example
Example 1

Input:
[[0,0],[2,1]]
[[1,2],[3,3]]
Output: [1,0]
Explanation:
Worker 1 grabs Bike 0 as they are closest (without ties), and Worker 0 is assigned Bike 1. So the output is [1, 0].
图片

Example 2

Input:
[[0,0],[1,1],[2,0]]
[[1,0],[2,2],[2,1]]
Output: [0,2,1]
Explanation:
Worker 0 grabs Bike 0 at first. Worker 1 and Worker 2 share the same distance to Bike 2, thus Worker 1 is assigned to Bike 2, and Worker 2 will take Bike 1. So the output is [0,2,1].

解法1：三元组排序。

class Solution {
public:
    /**
     * @param workers: workers' location
     * @param bikes: bikes' location
     * @return: assign bikes
     */
    vector<int> assignBikes(vector<vector<int>> &workers, vector<vector<int>> &bikes) {
        // write your code here
        int m = workers.size(), n = bikes.size();
        vector<pair<int, pair<int, int>>> data;  //<dist, <workdId, bikeId>>
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int dist = distance(workers[i], bikes[j]);
                data.push_back({dist, {i, j}});
            }
        }
        sort(data.begin(), data.end());
        vector<int> res(m, 0);
        unordered_set<int> workerSet, bikeSet;
        int count = 0;
        for (int i = 0; i < data.size(); i++) {
            int workerId = data[i].second.first;
            int bikeId = data[i].second.second;
            if (workerSet.find(workerId) == workerSet.end() && 
                bikeSet.find(bikeId) == bikeSet.end()) {
                workerSet.insert(workerId);
                bikeSet.insert(bikeId);
                res[workerId] = bikeId;
                count++;
                if (count == m) break;
            }
        }
        return res;
    }
private:
    int distance(vector<int> &place1, vector<int> &place2) {
        return abs(place1[0] - place2[0]) + abs(place1[1] - place2[1]);
    }
};