⚡Flashcard Drill➔
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

  1. Generate all (distance, workerIndex, bikeIndex) triples and sort them.
  2. Greedily assign: a triple is used only if both the worker and the bike are still unassigned.
  3. The tie-breaks fall out of the tuple ordering: distance first, then worker index, then bike index.
  4. 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] == -1 check: a worker could be assigned twice.
  • Forgetting the used_bike check: 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.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems