Contents

# Problem

There are `2N` people a company is planning to interview. The cost of flying the `i-th` person to city `A` is `costs[i]`, and the cost of flying the `i-th` person to city `B` is `costs[i]`.

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

## Constraint

• 1 <= `len(costs)` <= 100
• It is guaranteed that `len(costs)` is even.
• 1 <= `costs[i]`, `costs[i]` <= 1000

# Solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 `````` ``````func twoCitySchedCost(costs [][]int) int { st:= list{Val:-1} for idx := range costs { st.add(costs[idx],costs[idx], idx) } s:= 0 i:=0 stt := &st for stt != nil { i++ if i<=len(costs)/2{ s+=costs[stt.Idx] } else { s+=costs[stt.Idx] } stt = stt.Next } return s } type list struct { Next *list Val int Idx int } func (v *list) add(vala, valb, idx int) { if v.Val == -1 { v.Val=vala-valb v.Idx = idx return } val := vala-valb for v != nil { if val <= v.Val { ppp := *v *v = list{ Val: val, Idx:idx, Next: &ppp, } return } if v.Next == nil && val > v.Val{ v.Next = &list{ Val: val, Idx:idx, } return } v = v.Next } } func (v *list) print(){ for v!= nil{ fmt.Println(v) v = v.Next } } ``````