[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