In time, you will call me master -- Star Wars

Week 1 Two City Scheduling

• greedy
  

• description :

  • Given fee to go to City A cost[i][0]
  • Given fee to go to City B cost[i][1]
  • Calculate minimum fee to fly every person to a city such that exactly N people arrive in each city

• Solution :

  class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
  
        diff_cost = list()
        total_cost = 0
        for i in range(0, len(costs)):
            diff_cost.append(costs[i][1] - costs[i][0])
            total_cost += costs[i][0]
        diff_cost = sorted(diff_cost)
  
        for i in range(0, len(costs)//2):
            total_cost += diff_cost[i]
  
        return total_cost
  

• Solution detail :

  • suppose every person goes to City A
  • Calculate the difference between City A & City B
    • if difference is large means we have to increase budget
    • sort the difference between two cities
    • choose N//2 cities for people in City A to City B

• 中文版：

  • 給定 2D array 包含去 城市A (cost[i][0] ) & 城市B (cost[i][1] ) 費用
  • 計算最少費用並且 城市Ａ ＆ 城市Ｂ 人數要相等
  • 假設一開始所有人都在城市Ａ，計算出從城市Ａ移到城市Ｂ的差額費用
  • 排序並選出由小到大的 N//2 人數 移到城市Ｂ
  • 也就是 sum(所有人在城市Ａ) + （移到城市Ｂcost）

  Person | City A cost | City B cost | move fee City B | sort
  -------|-------------|-------------|-----------------------|
  0 | 10 | 20 | 10 | -350
  1 | 30 | 200 | 170 | -10
  2 | 400 | 50 | -350 | 10
  3 | 30 | 20 | -10 | 170

  result : 10 + 30 + 400 + 30 -350 - 10 = 110