Task 3 — Minimum Cost Assignment

Objective

Assign jobs to workers while minimizing the total assignment cost.

Each worker has a different cost for each job.

Each job must be assigned exactly once.

Each worker may receive at most one job.

Workers

Use:

W01
W02
W03
W04
W05

Jobs

Use:

J01
J02
J03
J04
J05

Cost Matrix

The cost of assigning each worker to each job is:

        J01  J02  J03  J04  J05

W01      9    2    7    8    6
W02      6    4    3    7    5
W03      5    8    1    8    4
W04      7    6    9    4    2
W05      8    5    6    3    7

Model

One possible representation is:

type AssignmentCost struct {
    WorkerID string
    JobID    string
    Cost     int
}

or:

type CostMatrix struct {
    Workers []string
    Jobs    []string
    Costs   [][]int
}

Result

A possible result model is:

type Assignment struct {
    WorkerID string
    JobID    string
    Cost     int
}

type AssignmentResult struct {
    Assignments []Assignment
    TotalCost   int
}

Required Function

Create a function conceptually equivalent to:

func FindMinimumCostAssignment(
    workers []string,
    jobs []string,
    costs [][]int,
) AssignmentResult

Rules

Every job must be assigned exactly once.

Every worker may be used at most once.

With equal worker and job counts:

every worker is used exactly once

Optimization Goal

Minimize:

sum of all assignment costs

Example Assignment

For example:

W01 -> J02 = 2
W02 -> J01 = 6
W03 -> J03 = 1
W04 -> J05 = 2
W05 -> J04 = 3

Total:

2 + 6 + 1 + 2 + 3 = 14

The implementation must determine whether this is optimal.

Do not assume that the example is the minimum.

Why Greedy Selection Fails

A simple rule such as:

for each worker, choose its cheapest available job

does not always produce the globally optimal assignment.

A locally cheap decision can force another worker into a very expensive assignment.

The complete assignment must be optimized as one problem.

Unequal Counts

The function should also support:

workers >= jobs

Unused workers are allowed.

If:

jobs > workers

the assignment is impossible.

Return an invalid result or explicit error.

Unsupported Assignment

Optionally support forbidden worker-job combinations using:

Allowed bool

or a special representation.

For example:

W02 cannot perform J04

Forbidden assignments must never appear in the result.

Tie-Breaking

If several assignments have the same minimum cost:

1. order assignments by JobID
2. compare WorkerID sequence lexicographically

Example:

J01 -> W01
J02 -> W03

is preferred over:

J01 -> W02
J02 -> W01

if both have the same total cost and the first sequence is lexicographically smaller.

Validation

Reject:

duplicate worker IDs
duplicate job IDs
negative cost
missing matrix rows
rows with incorrect length
empty worker ID
empty job ID
jobs > workers

Additional Test Case

Workers:

A
B
C

Jobs:

X
Y
Z

Costs:

      X   Y   Z

A     10   2   8
B      9   7   5
C      6   4   3

One possible assignment:

A -> Y = 2
B -> X = 9
C -> Z = 3

Total:

14

The implementation must verify whether a cheaper assignment exists.

Optional Extension — Skills

Add required job skills and worker skills.

An assignment is allowed only when:

worker satisfies all required job skills

Optimization is then performed only over valid combinations.

Optional Extension — Worker Capacity

Allow workers to receive more than one job.

Each job has:

Duration

and each worker has:

AvailableHours

The problem then becomes a more general capacity-constrained assignment problem.

Goal

This task introduces optimization over one-to-one relationships.

The implementation must reason about the complete assignment rather than evaluating each worker or job independently.