# 1029. Two City Scheduling

There are `2N`

people a company is planning to interview. The cost of flying the `i`

-th person to city `A`

is `costs[i][0]`

, and the cost of flying the `i`

-th person to city `B`

is `costs[i][1]`

.

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

people arrive in each city.

**Example 1:**

**Input: **

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

**Note:**

`1 <= costs.length <= 100`

- It is guaranteed that
`costs.length`

is even. `1 <= costs[i][0], costs[i][1] <= 1000`

class Solution { /** * @param Integer[][] $costs * @return Integer */ function twoCitySchedCost($costs) { usort($costs, function($arr1, $arr2) { return (abs($arr1[1]-$arr1[0]) < abs($arr2[1]-$arr2[0]) ) ? 1 : -1; }); $a = 0; $b = 0; $total = 0; foreach($costs as $c){ if($c[0] < $c[1]){ if($a < count($costs)/2){ $total += $c[0]; $a ++; } else { $total += $c[1]; $b ++; } } else{ if($b < count($costs)/2){ $total += $c[1]; $b ++; } else { $total += $c[0]; $a ++; } } } return $total; } }

16ms.

#### Thoughts:

- This code was used for the contest, so it’s not well structured (in terms of redundancy)
- The basic idea:
- Sort by switching cost (price diff), DESC.
- then for each person, assign to lower cost city until full.
- in case of full, assign to city with higher cost

- Since sorted by price diff, at the time one city is full, the cost to switch remaining people to the second choice is the lowest

#### If I’m a interviewer:

- Let’s try three cities….
- What about the capacity of each city is specified?
- And what about the capacity is flexible and within a range provided?

## 0 Comments