← Static tasks

1057. Campus Bikes

leetcode medium

#array#csharp#leetcode#math#medium#sort

Task

В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Пример:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]

Output: [1,0]

C# solution

matched/original
public class Solution {
    public int[] AssignBikes(int[][] workers, int[][] bikes) {
        var pairs = new List<(int distance, int workerIdx, int bikeIdx)>();
        
        for (int i = 0; i < workers.Length; i++) {
            for (int j = 0; j < bikes.Length; j++) {
                int distance = Math.Abs(workers[i][0] - bikes[j][0]) + Math.Abs(workers[i][1] - bikes[j][1]);
                pairs.Add((distance, i, j));
            }
        }
        
        pairs.Sort((a, b) => {
            int result = a.distance.CompareTo(b.distance);
            if (result == 0) {
                result = a.workerIdx.CompareTo(b.workerIdx);
                if (result == 0) {
                    result = a.bikeIdx.CompareTo(b.bikeIdx);
                }
            }
            return result;
        });
        
        int[] result = new int[workers.Length];
        bool[] bikeTaken = new bool[bikes.Length];
        bool[] workerAssigned = new bool[workers.Length];
        
        Array.Fill(result, -1);
        
        foreach (var pair in pairs) {
            if (!workerAssigned[pair.workerIdx] && !bikeTaken[pair.bikeIdx]) {
                result[pair.workerIdx] = pair.bikeIdx;
                bikeTaken[pair.bikeIdx] = true;
                workerAssigned[pair.workerIdx] = true;
            }
        }
        
        return result;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& AssignBikes(int[][] workers, int[][] bikes) {
        var pairs = new List<(int distance, int workerIdx, int bikeIdx)>();
        
        for (int i = 0; i < workers.size(); i++) {
            for (int j = 0; j < bikes.size(); j++) {
                int distance = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
                pairs.push_back((distance, i, j));
            }
        }
        
        pairs.Sort((a, b) => {
            int result = a.distance.CompareTo(b.distance);
            if (result == 0) {
                result = a.workerIdx.CompareTo(b.workerIdx);
                if (result == 0) {
                    result = a.bikeIdx.CompareTo(b.bikeIdx);
                }
            }
            return result;
        });
        
        vector<int>& result = new int[workers.size()];
        bool[] bikeTaken = new bool[bikes.size()];
        bool[] workerAssigned = new bool[workers.size()];
        
        Array.Fill(result, -1);
        
        foreach (var pair in pairs) {
            if (!workerAssigned[pair.workerIdx] && !bikeTaken[pair.bikeIdx]) {
                result[pair.workerIdx] = pair.bikeIdx;
                bikeTaken[pair.bikeIdx] = true;
                workerAssigned[pair.workerIdx] = true;
            }
        }
        
        return result;
    }
}

Java solution

matched/original
import java.util.*;

public class Solution {
    public int[] assignBikes(int[][] workers, int[][] bikes) {
        List<int[]> pairs = new ArrayList<>();
        
        for (int i = 0; i < workers.length; i++) {
            for (int j = 0; j < bikes.length; j++) {
                int distance = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
                pairs.add(new int[]{distance, i, j});
            }
        }
        
        pairs.sort((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            if (a[1] != b[1]) return a[1] - b[1];
            return a[2] - b[2];
        });
        
        int[] result = new int[workers.length];
        boolean[] bikeTaken = new boolean[bikes.length];
        boolean[] workerAssigned = new boolean[workers.length];
        
        Arrays.fill(result, -1);
        
        for (int[] pair : pairs) {
            int workerIdx = pair[1];
            int bikeIdx = pair[2];
            if (!workerAssigned[workerIdx] && !bikeTaken[bikeIdx]) {
                result[workerIdx] = bikeIdx;
                bikeTaken[bikeIdx] = true;
                workerAssigned[workerIdx] = true;
            }
        }
        
        return result;
    }
}

JavaScript solution

matched/original
function assignBikes(workers, bikes) {
    const pairs = [];
    
    for (let i = 0; i < workers.length; i++) {
        for (let j = 0; j < bikes.length; j++) {
            const distance = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
            pairs.push([distance, i, j]);
        }
    }
    
    pairs.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        if (a[1] !== b[1]) return a[1] - b[1];
        return a[2] - b[2];
    });
    
    const result = Array(workers.length).fill(-1);
    const bikeTaken = Array(bikes.length).fill(false);
    const workerAssigned = Array(workers.length).fill(false);
    
    for (const [distance, workerIdx, bikeIdx] of pairs) {
        if (!workerAssigned[workerIdx] && !bikeTaken[bikeIdx]) {
            result[workerIdx

Python solution

matched/original
def assignBikes(workers, bikes):
    pairs = []
    
    for i, (wx, wy) in enumerate(workers):
        for j, (bx, by) in enumerate(bikes):
            distance = abs(wx - bx) + abs(wy - by)
            pairs.append((distance, i, j))
    
    pairs.sort()
    
    result = [-1] * len(workers)
    bike_taken = [False] * len(bikes)
    worker_assigned = [False] * len(workers)
    
    for distance, worker_idx, bike_idx in pairs:
        if not worker_assigned[worker_idx] and not bike_taken[bike_idx]:
            result[worker_idx] = bike_idx
            bike_taken[bike_idx] = True
            worker_assigned[worker_idx] = True
    
    return result

Go solution

matched/original
package main

import (
    "fmt"
    "sort"
    "math"
)

type Pair struct {
    distance int
    workerIdx int
    bikeIdx int
}

func assignBikes(workers [][]int, bikes [][]int) []int {
    var pairs []Pair
    
    for i := 0; i < len(workers); i++ {
        for j := 0; j < len(bikes); j++ {
            distance := int(math.Abs(float64(workers[i][0] - bikes[j][0])) + math.Abs(float64(workers[i][1] - bikes[j][1])))
            pairs = append(pairs, Pair{distance, i, j})
        }
    }
    
    sort.Slice(pairs, func(a, b int) bool {
        if pairs[a].distance != pairs[b].distance {
            return pairs[a].distance < pairs[b].distance
        }
        if pairs[a].workerIdx != pairs[b].workerIdx {
            return pairs[a].workerIdx < pairs[b].workerIdx
        }
        return pairs[a].bikeIdx < pairs[b].bikeIdx
    })
    
    result := make([]int, len(workers))
    for i := range result {
        result[i] = -1
    }
    bikeTaken := make([]bool, len(bikes))
    workerAssigned := make([]bool, len(workers))
    
    for _, pair := range pairs {
        if !workerAssigned[pair.workerIdx] && !bikeTaken[pair.bikeIdx] {
            result[pair.workerIdx] = pair.bikeIdx
            bikeTaken[pair.bikeIdx] = true
            workerAssigned[pair.workerIdx] = true
        }
    }
    
    return result
}

func main() {
    workers := [][]int{{0, 0}, {2, 1}}
    bikes := [][]int{{1, 2}, {3, 3}}
    fmt.Println(assignBikes(workers, bikes)) // Output: [1, 0]
}

Explanation

Algorithm

Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.

Отсортируй список пар по расстоянию, а затем по индексу работника и велосипеда.

Назначь велосипеды работникам, следуя отсортированному списку пар и отслеживая, какие работники и велосипеды уже были использованы.

Заполни и верни массив назначений.

😎