Leetcode: Two City Scheduling

Two City Scheduling

Similar Problems:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:
```// Blog link: https://code.dennyzhang.com/two-city-scheduling
// Basic Ideas: greedy
//  Get the absolute difference for each person
//  Start to settle down with persons whos difference are bigger
// Complexity: Time O(n*log(n)), Space O(1)
import "sort"
func abs(v int) int {
if v<0 { return -v }
return v
}

func twoCitySchedCost(costs [][]int) int {
sort.Slice(costs, func(i, j int) bool {
return abs(costs[i][0]-costs[i][1]) > abs(costs[j][0]-costs[j][1])
})

N := len(costs)/2
cityA, cityB := N, N
res := 0
for _, cost := range costs {
if cityA == 0 {
res += cost[1]
} else if cityB == 0 {
res += cost[0]
} else {
if cost[0] < cost[1] {
res += cost[0]
cityA--
} else {
res += cost[1]
cityB--
}
}
}
return res
}
```

Share It, If You Like It.