Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

Solution: Two City Scheduling

Understand how to solve the Two City Scheduling problem by applying a greedy algorithm that sorts candidates based on cost differences. This lesson guides you to allocate half the candidates to each city to achieve minimal total cost. Learn the step-by-step approach, including sorting and cost calculation, and analyze the time and space complexity of the solution.

We'll cover the following...

Statement

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