Задача: 1057. Campus Bikes
Сложность: medium

В городке, изображенном на плоскости 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]

👨‍💻 Алгоритм:

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

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

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

😎 Решение:

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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний