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

Two City Scheduling

Explore how to solve the Two City Scheduling problem by applying greedy algorithms to minimize total costs. Understand how to assign candidates evenly between two locations while considering individual travel expenses. This lesson helps build skills in optimization and cost-effective decision-making for coding interviews.

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

Constraints:

  • 2≤2 \leq costs.length ≤100\leq 100
  • costs.length is even
  • 1≤aCosti,bCosti≤10001 \leq aCost_i, bCost_i \leq 1000

Examples

canvasAnimation-image
1 / 3

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:

Two City Scheduling

1.

What is the minimum cost to invite every person to two different cities such that the same number of people arrive in each city if the costs are as follows?

[10, 15], [10, 20], [10, 25], [10, 30]?

A.

40

B.

55

C.

75

1 / 2

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.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4
5

Try it yourself

Implement your solution in main.py in the following coding playground.

Python
usercode > main.py
def two_city_scheduling(costs):

  

  # Replace this placeholder return statement with your code

  return -1
Two City Scheduling