0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ – Learner Jun 5 '20 at 0:44
1
$\begingroup$

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)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ the problem definition in the wiki says that the sets should be of the same size. In our case, it is from N -> k .Is it the same problem ? $\endgroup$ – Learner Jun 5 '20 at 6:37
  • $\begingroup$ @Learner No, it's from $kn$ to $kn$. We have $kn$ people and $kn$ jobs (each job is copied $n$ times). $\endgroup$ – orlp Jun 5 '20 at 8:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.