Three City Scheduling

Question

I came across the following interview question

There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].

Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

The solution to this involves greedy approach, where we sort the array based on the "profit" parameter. profit of choosing city A for a candidate i is defined as costs[i][1] - costs[i][0] and choose the top half elements from the sorted array to go to A and rest to B.

What if this question is modified to 3 cities and you have find optimal partition of n/3 chunks? Will greedy algorithm still work?

Answer 1

Generalizing with $kn$ people and $k$ cities we can see "move to city $j$" as a task. Furthermore, we have $n$ copies of each task. For all copies of a task $j$, the cost for person $i$ to move to that task is $c_{i, j}$.

But now the problem is a direct instance of the balanced assignment problem, with complexity $O((kn)^3)$.