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

Solution: Two City Scheduling

Explore the greedy algorithm solution for the Two City Scheduling problem. This lesson helps you understand how to minimize total interview costs by strategically assigning half the candidates to each city based on cost differences. You'll learn to sort candidates by cost advantage and calculate the minimum total cost with O(n log n) time complexity, improving your problem-solving skills for optimization challenges.

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