Solution: Two City Scheduling

Let's solve the Two City Scheduling problem using the Greedy pattern.


A recruiter plans to hire n\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]=[aCosti,bCosti]costs[i] = [aCost_i, bCost_i], the cost of inviting the ithi^{th} person to City AA is aCostiaCost_i, and the cost of inviting the same person to City BB is bCostibCost_i.

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

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.