Leetcode June challenge ( Two City Scheduling )

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 ACalculate the difference between City A & City Bif difference is large means we have to increase budgetsort the difference between two citieschoose 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