11066. Campus Bikes II

You are given the coordinates of N workers and M bikes on a 2D grid (N <= M). Assign exactly one distinct bike to each worker so that the total Manhattan distance is as small as possible.

The Manhattan distance between points (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|.

Implement class BikeAllocator with method minBikeSum that takes workersArr and bikesArr as String[] where each entry is "x,y", and returns the minimum possible total distance.

Examples

Example 1:
workersArr = ["0,1","2,0"]
bikesArr   = ["1,2","3,3"]
BikeAllocator.minBikeSum(workersArr, bikesArr) -> 6
Explanation:
Assign bike "1,2" to worker "0,1" (distance 2) and bike "3,3" to worker "2,0" (distance 4). Total = 2 + 4 = 6.

Example 2:
workersArr = ["0,0","1,1","2,2"]
bikesArr   = ["1,0","2,1","3,3"]
BikeAllocator.minBikeSum(workersArr, bikesArr) -> 4
Explanation:
One optimal assignment is:
- "0,0" -> "1,0" (1)
- "1,1" -> "2,1" (1)
- "2,2" -> "3,3" (2)
Total = 1 + 1 + 2 = 4.

Constraints

  • 1 <= workersArr.length <= bikesArr.length <= 11
  • Each string in workersArr and bikesArr is formatted as "x,y" with 0 <= x, y <= 2000
  • All worker positions are distinct; all bike positions are distinct
  • N = workersArr.length, M = bikesArr.length, with N <= M




Please use Laptop/Desktop or any other large screen to add/edit code.