1029. Two City Scheduling
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][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.Constraint
- 1 <=
len(costs)<= 100 - It is guaranteed that
len(costs)is even. - 1 <=
costs[i][0],costs[i][1]<= 1000
Solution
Linked list
func twoCitySchedCost(costs [][]int) int {
st:= list{Val:-1}
for idx := range costs {
st.add(costs[idx][0],costs[idx][1], idx)
}
s:= 0
i:=0
stt := &st
for stt != nil {
i++
if i<=len(costs)/2{
s+=costs[stt.Idx][0]
} else {
s+=costs[stt.Idx][1]
}
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
}
}