[LeetCode] weekly-contest-13 two-city-scheduling

這週weekly contest

https://leetcode.com/contest/weekly-contest-133/problems/two-city-scheduling/

隨便挑一題比較簡單的來寫XD

直覺想法，應該是任一user在A,B之間要選一個相對成本較低的

但其中一個user選了A城市，那必有一個user要選城市B (因為兩邊人數要一致都為n/2)

所以其實要看相對應user之間的相對成本

先sort每個人兩個city的相對成本差異(這步是我是挑用python寫的原因XD)
頭尾兩個user相比，如果City A的相對成本比較小就選A，e往後，反之則選B，e往前
如果A or B已經達到N/2了，剩下的user就都去另一個city

class Solution(object):
    def twoCitySchedCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        ans, s, length = 0, 0, len(costs)
        e = length-1
        
        costs.sort(key=lambda costs: (costs[0]-costs[1]))
        
        while(s <= e):
            if s == length/2:
                ans += costs[e][1]
                e -= 1
            elif e == length/2:
                ans += costs[s][0]
                s += 1
            elif(abs(costs[s][0]-costs[s][1]) < abs(costs[e][0]-costs[e][1])):
                ans += costs[s][0]
                s += 1
            else:
                ans += costs[e][1]
                e -= 1
        return ans

class Solution(object):

def twoCitySchedCost(self, costs):

"""

:type costs: List[List[int]]

:rtype: int

"""

ans, s, length = 0, 0, len(costs)

e = length-1

costs.sort(key=lambda costs: (costs[0]-costs[1]))

while(s <= e):

if s == length/2:

ans += costs[e][1]

e -= 1

elif e == length/2:

ans += costs[s][0]

s += 1

elif(abs(costs[s][0]-costs[s][1]) < abs(costs[e][0]-costs[e][1])):

ans += costs[s][0]

s += 1

else:

ans += costs[e][1]

e -= 1

return ans

[LeetCode] weekly-contest-13 two-city-scheduling

請按讚：

相關

發表者：user

分享此文：

請按讚：

相關

發表者：user