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], and the cost of flying the i-th person to city B is costs[i].
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] - costs[i] 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?