专栏首页编程理解Leetcode 1029. 两地调度

Leetcode 1029. 两地调度

题目描述

公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0],飞往 B 市的费用为 costs[i][1]。

返回将每个人都飞到某座城市的最低费用,要求每个城市都有 N 人抵达。

示例 1:

输入:[[10,20],[30,200],[400,50],[30,20]]

输出:110

解释:

第一个人去 A 市,费用为 10。 第二个人去 A 市,费用为 30。 第三个人去 B 市,费用为 50。 第四个人去 B 市,费用为 20。

最低总费用为 10 + 30 + 50 + 20 = 110,每个城市都有一半的人在面试。

解法

以 sub 数组表示去 B 市与去 A 市的代价差值,即 sub[i] = cost[i][1] - cost[i][0],对 sub 递减排序。不妨以 ret 表示 2N 人全部去了 B 市的总费用,则 ret - sum(sub[:N]) 表示有 N 人去了 A 市的最低总费用。

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        ret,sub=0,[]
        for i in costs:
            ret+=i[1]
            sub.append(i[1]-i[0])
        sub.sort(reverse=True)
        return ret-sum(sub[:len(costs)//2])

题中为一半的人去了 A 市,该方式可同样计算出总人数的三分之一、四分之一人数去 A 市的最小费用问题。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 3. 无重复字符的最长子串

    输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

    zhipingChen
  • Leetcode 136. 只出现一次的数字

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

    zhipingChen
  • 排序算法(一):冒泡排序

    冒泡排序是一种通过交换元素位置实现的稳定排序方式,其特点是每一轮排序后,都会在首端或尾端产生一个已排序元素,就像水泡不断上浮一样,通过多次排序,最终所有元素变得...

    zhipingChen
  • [每日一题]最大公约数与最小公倍数

    今天给大家分享的是一道比较基本的题,相信好多同学都会了吧 题目描述 输入两个正整数m和n,求其最大公约数和最小公倍数。 输入 两个整数 输出 最大公约数,最...

    编程范 源代码公司
  • k8s实践(十二):Prometheus Operator监控Kubernetes集群

    Prometheus是一个开源系统监控和警报工具包,最初是在soundcloud构建的。自2012年成立以来,许多公司和组织都采用了Prometheus,该项目...

    loong576
  • 多线程通信的三大法器,你真的会用吗?

    wait, notify, notifyAll 是多线程之间通信最重要的 3 个方法,今天,栈长给大家普及一下它们的知识要点及应用实战。

    Java技术栈
  • Facebook教你如何玩转大数据

    不论“大数据”概念是不是个陷阱,我们的时代,互联网巨头坐拥海量信息是无人可以否认的事实,社区产品和社交产品赖以生存的基础就是从用户那儿来的数据。 他们都...

    静一
  • Fundamentals of speech signal processing

    PDF版资料下载:链接:http://pan.baidu.com/s/1hrKntkw 密码:f2y9

    互联网金融打杂
  • OAuth2 登陆授权代码示例

    现如今各大互联网公司都提供了自己的开放平台,这给第三方开发者提供了不少机会,这些平台为了让开发者访问平台内部被保护的特定资源,使用了OAuth2作为登陆授权协议...

    java达人
  • 使用ABAP和JavaScript代码生成PDF文件的几种方式

    详细步骤参考我的博客Convert word document into PDF via Adobe Livecycle Enterprise service

    Jerry Wang

扫码关注云+社区

领取腾讯云代金券