# 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. `1 <= costs.length <= 100`
2. It is guaranteed that `costs.length` is even.
3. `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?