# Greedy - Two City Scheduling

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

Greedy, Two Pointers

## Problem

A company is planning to interview `2n`

people. Given the array `costs`

where `costs[i] = [aCosti, bCosti]`

, the cost of flying the `ith`

person to city `a`

is `aCosti`

, and the cost of flying the `ith`

person to city `b`

is `bCosti`

.

Return *the minimum cost to fly every person to a city* such that exactly `n`

people arrive in each city.

**Example 1:**

1
2
3
4
5
6
7
8
9
10

Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation:
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.
The total minimum cost is 10 + 30 + 50 + 20 = 110 to
have half the people interviewing in each city.

**Example 2:**

1
2

Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859

**Example 3:**

1
2
3

Input: costs = [[515,563],[451,713],[537,709],
[343,819],[855,779],[457,60],[650,359],[631,42]]
Output: 3086

## Solution

There is a way to solve this using `dfs()`

, however if one just think beyond the complex solution, there is a much easier solution.

Below are simple three steps.

- Calculate
`B-A`

- Sort the values
- The first half of the sorted list would need to go to city
`B`

(as going to city`A`

will be very costly for them) and second half to city`A`

(As city`B`

will be very costly for them). - Now calculate the
`total_cost`

.

We are here trying to minimize the cost by sorting the cost difference between two cities.

Start by calculating the difference can the sort the values.

1
2
3
4
5

difference = []
for A, B in costs:
difference.append([B-A, A, B])
difference.sort()

Now, loop though add cost for city `B`

from 1st half of the array then cost of the city `A`

from 2nd half of the array.

1
2
3
4
5
6
7

cost = 0
for i in range(len(difference)):
if i < (difference)//2 # first half
cost+= difference[i][2] # 3rd entry is B
else:
cost+= difference[i][1] # 2nd entry is A
return cost

## Final Code

Here is the full code.

1
2
3
4
5
6

def two_city_sched_cost(costs):
difference = []
for A, B in costs:
difference.append([B-A, A, B])
difference.sort()