[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