NeetCode #529LC-1057MediumHeap / Priority QueueNC Algo100
← Back to All Problems#529 · #1057 · Campus Bikes(校园自行车分配)
📌 Problem Statement & Constraints
Given
workers and bikes coordinates on a grid, assign each worker a distinct bike minimising the total Manhattan distance, with tie-breaks: smallest worker index first, then smallest bike index. Return the assignment. Constraints: 1 <= workers.length <= bikes.length <= 1000.💡 Core Algorithmic Approaches
- Generate all
(distance, workerIndex, bikeIndex)triples and sort them. - Greedily assign: a triple is used only if both the worker and the bike are still unassigned.
- The tie-breaks fall out of the tuple ordering: distance first, then worker index, then bike index.
- The greedy is optimal because the sorted order processes the globally best remaining pairing first.
💻 Benchmark Python3 Implementation
class Solution:
def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:
triples = []
for i, (wx, wy) in enumerate(workers):
for j, (bx, by) in enumerate(bikes):
d = abs(wx - bx) + abs(wy - by) # Manhattan distance
triples.append((d, i, j))
triples.sort() # distance, then worker, then bike
res = [-1] * len(workers)
used_bike = [False] * len(bikes)
assigned = 0
for d, i, j in triples:
if res[i] == -1 and not used_bike[j]:
res[i] = j
used_bike[j] = True
assigned += 1
if assigned == len(workers):
break
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(w * b log(w * b)): generating and sorting all pairs.
💾 Space Complexity
O(w * b) for the triples.
⚠️ Interview Pitfalls & Follow-ups
- Using Euclidean distance: the problem specifies Manhattan distance.
- Sorting by distance only: the tuple ordering provides the required tie-breaks automatically.
- Assigning without the
res[i] == -1check: a worker could be assigned twice. - Forgetting the
used_bikecheck: two workers could share a bike.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.