1029-两地调度

1029. 两地调度

• 按照每个人去A、B两地的路费差进行排序，排好序后，前半部分人去A地，后半部分人去B地
• 以 [[10,20],[30,200],[400,50],[30,20]] 为例，两地的差分别为[-10,-170,350,10]
  • 相对于B地，第1个人花费的代价最大，所以去A地；然后第0个人去A地也相对划算一些。因此这两人花费：30+10
  • 相对于B地，第3个人去B地相对划算一些；第2个人去B地最划算。因此这两人花费：20+50
  • 总花费：30+10+20+50=110

class Solution(object):
    def twoCitySchedCost(self, costs):
        # 按照这个人AB两地的路费差值排序
        costs.sort(key=lambda x: x[0] - x[1])

        total = 0
        n = len(costs) // 2
        # cost分成两部分，前半部分去A地，后半部分去B地
        for i in range(n):
            total += costs[i][0] + costs[i + n][1]
        return total

# s=Solution()
# costs=[[10,20],[30,200],[400,50],[30,20]]
# print(s.twoCitySchedCost(costs))