Katkat
Back

Minimize Travel Assignment Cost

BloombergSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to minimize costs when assigning workers to multiple destinations, requiring an application of dynamic programming to manage fixed capacity constraints.

Problem Statement

You are managing a team of N employees who need to be assigned to M different regional offices. Each office j requires exactly C_j employees, and the total number of employees equals the total capacity across all offices (i.e., sum of C_j = N).

You are given a cost matrix costs, where costs[i][j] represents the cost of assigning employee i to office j. Your goal is to assign every employee to exactly one office such that the total cost is minimized.

Implement the following function: def min_assignment_cost(costs, capacities):

Constraints

  • N (number of employees) is up to 20.
  • M (number of offices) is up to 20.
  • costs[i][j] are non-negative integers.

Example 1

Input: costs = [[10, 2], [1, 5], [8, 3]] capacities = [1, 2]

Output: 6 Explanation: Assign employee 0 to office 1 (cost 2), employee 1 to office 0 (cost 1), and employee 2 to office 1 (cost 3). Total cost = 2 + 1 + 3 = 6.

Example 2

Input: costs = [[5, 10], [2, 1], [3, 8], [9, 4]] capacities = [2, 2]

Output: 15

Edge Cases

  • Only one office available.
  • N = M (one-to-one assignment).
  • Costs are uniform.

Hints

Hint 1

Since the number of employees is small (N <= 20), consider representing the set of assigned employees using a bitmask.

Hint 2

Define your state as `dp(employee_index, current_capacities_tuple)`, where `current_capacities_tuple` tracks remaining spots in each office.

Hint 3

Use memoization to store results for combinations of assigned employees and remaining office capacities to avoid redundant calculations.

Follow-up questions

  • How does the time complexity change if we increase the number of employees to 100 while keeping the number of offices small?
  • If each office also had a minimum requirement of employees to function, how would you incorporate that into your state representation?
  • Could this problem be modeled as a Min-Cost Max-Flow problem? What would be the nodes and edges?