Сложность: medium
На кампусе, представленном в виде двумерной сетки, есть n рабочих и m велосипедов, где n <= m. Каждый рабочий и велосипед имеют координаты на этой сетке.
Мы назначаем каждому рабочему уникальный велосипед таким образом, чтобы сумма Манхэттенских расстояний между каждым рабочим и назначенным ему велосипедом была минимальной.
Верните минимально возможную сумму Манхэттенских расстояний между каждым рабочим и назначенным ему велосипедом.
Манхэттенское расстояние между двумя точками p1 и p2 вычисляется как Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Пример:
Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]
👨💻 Алгоритм:
1⃣Для каждого рабочего, начиная с рабочего с индексом 0, пройдите по всем велосипедам и назначьте велосипед рабочему, если он доступен (visited[bikeIndex] = false). После назначения велосипеда отметьте его как недоступный (visited[bikeIndex] = true). Добавьте Манхэттенское расстояние от этого назначения к общей текущей сумме расстояний, представленной currDistanceSum, и выполните рекурсивный вызов для следующего рабочего.
2⃣Когда рекурсивный вызов завершится, сделайте велосипед снова доступным, установив visited[bikeIndex] в false. Если мы назначили велосипеды всем рабочим, сравните currDistanceSum с smallestDistanceSum и обновите smallestDistanceSum соответственно.
3⃣Перед назначением любого велосипеда рабочему, проверьте, если currDistanceSum уже больше или равен smallestDistanceSum. Если это так, пропустите остальных рабочих и вернитесь. Это связано с тем, что currDistanceSum может только увеличиваться, и таким образом мы не найдем лучший результат, чем smallestDistanceSum, используя текущую комбинацию рабочих и велосипедов.
😎 Решение:
class Solution {
var smallestDistanceSum = Int.max
var visited = [Bool](repeating: false, count: 10)
func findDistance(_ worker: [Int], _ bike: [Int]) -> Int {
return abs(worker[0] - bike[0]) + abs(worker[1] - bike[1])
}
func minimumDistanceSum(_ workers: [[Int]], _ workerIndex: Int,
_ bikes: [[Int]], _ currDistanceSum: Int) {
if workerIndex >= workers.count {
smallestDistanceSum = min(smallestDistanceSum, currDistanceSum)
return
}
if currDistanceSum >= smallestDistanceSum {
return
}
for bikeIndex in 0..<bikes.count {
if !visited[bikeIndex] {
visited[bikeIndex] = true
minimumDistanceSum(workers, workerIndex + 1, bikes,
currDistanceSum + findDistance(workers[workerIndex], bikes[bikeIndex]))
visited[bikeIndex] = false
}
}
}
func assignBikes(_ workers: [[Int]], _ bikes: [[Int]]) -> Int {
minimumDistanceSum(workers, 0, bikes, 0)
return smallestDistanceSum
}
}Ставь 👍 и забирай 📚 Базу знаний