Two City Scheduling

Statement

A recruiter plans to hire $\textbf{\textit{n}}$ people and conducts their interviews at two different locations of the company. He evaluates the cost of inviting candidates to both these locations. The plan is to invite 50% at one location, and the rest at the other location, keeping costs to a minimum.

We are given an array, costs, where $costs[i] = [aCost_i, bCost_i]$, the cost of inviting the $i^{th}$ person to City $A$ is $aCost_i$, and the cost of inviting the same person to City $B$ is $bCost_i$.

You need to determine the minimum cost to invite all the candidates for the interview such that exactly $\textbf{\textit{n/2}}$ people are invited in each city.

Examples

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Figure it out

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Try it yourself

Implement your solution in TwoCityScheduling.java in the following coding playground.