Solution: 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.