[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之間的相對成本

1. 先sort每個人兩個city的相對成本差異(這步是我是挑用python寫的原因XD)
2. 頭尾兩個user相比，如果City A的相對成本比較小就選A，e往後，反之則選B，e往前
3. 如果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