# Three City Scheduling

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?

• Can i extend the greedy algorithm and modify the "profit" function to something like Math.min(costs[i][1], costs[i][2]) - costs[i][0]? Then assign the top n/3 candidates to city A. For the rest of the 2n/3, i can defer to the original question – Learner Jun 5 '20 at 0:44

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)$$.
• @Learner No, it's from $kn$ to $kn$. We have $kn$ people and $kn$ jobs (each job is copied $n$ times). – orlp Jun 5 '20 at 8:30