這週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