LeetCode 1094. 拼车:优先队列
【LetMeFly】1094.拼车:优先队列
力扣题目链接:https://leetcode.cn/problems/car-pooling/
车上最初有 capacity 个空座位。车 只能 向一个方向行驶(也就是说,不允许掉头或改变方向)
给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客,接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时,返回 true,否则请返回 false。
示例 1:
输入:trips = [[2,1,5],[3,3,7]], capacity = 4 输出:false
示例 2:
输入:trips = [[2,1,5],[3,3,7]], capacity = 5 输出:true
提示:
1 <= trips.length <= 1000trips[i].length == 31 <= numPassengersi <= 1000 <= fromi < toi <= 10001 <= capacity <= 105
方法一:优先队列
首先二话不说对trips按“上车地点”为依据从小到大排个序。
接着创建一个优先队列,用于存放“已上车的人”。优先队列的排序依据是“先下车的人优先”。
使用一个变量记录当前车上的人数,遍历trips数组:
让优先队列中,不晚于此位置的人下车;
让这批人上车。
期间若出现超载的情况则返回false,否则返回true。
- 时间复杂度 O ( n log n ) O(n\log n) O(nlogn),其中 n = l e n ( t r i p s ) n=len(trips) n=len(trips)
- 空间复杂度 O ( n ) O(n) O(n)
AC代码
C++
class Solution {
public:bool carPooling(vector<vector<int>>& trips, int capacity) {sort(trips.begin(), trips.end(), [](const vector<int>& a, const vector<int>& b) {return a[1] < b[1];});int nowPeopleCnt = 0;auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;};priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> nowPeople(cmp);for (vector<int>& trip : trips) {int num = trip[0], from = trip[1], to = trip[2];while (nowPeople.size() && nowPeople.top().second <= from) {nowPeopleCnt -= nowPeople.top().first;nowPeople.pop();}nowPeopleCnt += num;if (nowPeopleCnt > capacity) {return false;}nowPeople.push({num, to});}return true;}
};
Python
# from typing import List
# import heapqclass Solution:def carPooling(self, trips: List[List[int]], capacity: int) -> bool:trips.sort(key=lambda x: x[1])nowPeopleCnt = 0nowPeople = []for num, from_, to in trips:while nowPeople and nowPeople[0][0] <= from_:nowPeopleCnt -= nowPeople[0][1]heapq.heappop(nowPeople)nowPeopleCnt += numif nowPeopleCnt > capacity:return Falseheapq.heappush(nowPeople, (to, num))return True
同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/134751973
相关文章:
LeetCode 1094. 拼车:优先队列
【LetMeFly】1094.拼车:优先队列 力扣题目链接:https://leetcode.cn/problems/car-pooling/ 车上最初有 capacity 个空座位。车 只能 向一个方向行驶(也就是说,不允许掉头或改变方向) 给定整数 capacity 和一个数组…...
项目开发维护技术文档(总结梳理)
目录 一、项目背景 二、架构设计 1.技术栈 2.架构图 3.代码结构 三、模块划分 1.用户模块 2.商品模块 四、开发规范 1.命名规范 2.代码格式 3.版本控制 五、部署流程 1.环境要求 2.部署流程 六、问题解决 1.数据库连接异常 2.Redis缓存失效 七、参考资料 项…...
01_学习使用javax_ws_rs_上传文件
文章目录 1 前言2 Maven 依赖3 上传接口4 如何解析 MultipartFormDataInput5 结语 1 前言 使用 Spring MVC 来处理文件上传,想必是大家耳熟能详的了,如下代码: ResponseBody PostMapping("/upload") public String upload(Request…...
MFC 发布CLXHHandleEngine动态库1.0.0.0版本
第一版发布以下功能,此项目使用VS2013创建,项目配置包括Unicode的Mdd,md与多字节版本: //MFC Grid表格 #include "../MFCGridCtrl/GridCtrl.h" //使用AES与Base64加密解密可以与java中的AES加解密衔接 //AES加密解密 #include &q…...
MicroPython 基于microdot框架搭建网页服务器
MicroPython 基于microdot框架搭建网页服务器 简介简单demo 简介 Microdot是一个极简的Python web框架,灵感来自于Flask,它被设计用来运行在资源有限的系统上,如微控制器。它运行在标准的Python和MicroPython上。 API参考microdot 资源下载m…...
FL Studio21.2汉化永久中文语言包
FL Studio21.2这款软件在国内被广泛使用,因此又被称为"水果"。它提供音符编辑器,可以针对作曲者的要求编辑出不同音律的节奏,例如鼓、镲、锣、钢琴、笛、大提琴、筝、扬琴等等任何乐器的节奏律动。此外,它还提供了方便快…...
Glide结合OkHttp保证短信验证接口携带图形验证码接口返回Cookie值去做网络请求
一、实现效果 二、步骤 注意:仅展示核心部分代码 1、导入依赖 api com.github.bumptech.glide:glide:4.10.0 kapt com.github.bumptech.glide:compiler:4.10.0 api com.squareup.okhttp3:okhttp:3.11.0 api com.squareup.okhttp3:logging-interceptor:3.11.02、自…...
怎样用Ajax提交from表单并接收其中的json数据
怎样用Ajax提交表单并接收其中的json数据 需求:实现点击按钮后,数据以表单形式提交至服务器,并接收来自服务器的返回数据。过程中页面不刷新。 AJAX 不是新的编程语言,而是一种使用现有标准的新方法。AJAX 是与服务器交换数据并…...
【动态规划】LeetCode-746LCR 088.使用最小花费爬楼梯
🎈算法那些事专栏说明:这是一个记录刷题日常的专栏,每个文章标题前都会写明这道题使用的算法。专栏每日计划至少更新1道题目,在这立下Flag🚩 🏠个人主页:Jammingpro 📕专栏链接&…...
Unity 接入TapADN播放广告时闪退 LZ4JavaSafeCompressor
通过跟踪安卓日志,发现报如下错误 Didnt find class "com.tapadn.lz4.LZ4JavaSafeCompressor" 解决方案: 去掉Minify这边的勾选,再打包即可。...
【九】linux下部署frp客户端服务端实践(内网穿透)
linux下部署frp客户端服务端实践 简介: 今天有一个这样的需求,部署在公司内部局域网虚拟机上的服务需要在外网能够访问到,这不就是内网穿透的需求吗,之前通过路由器实现过,现在公司这块路由器不具备这个功能了&#x…...
华为1+x网络系统建设与运维(中级)-练习题2
一.设备命令 LSW1 [Huawei]sys LSW1 同理可得,给所有设备改名 二.VLAN LSW1 [LSW1]vlan ba 10 20 [LSW1]int g0/0/1 [LSW1-GigabitEthernet0/0/1]port link-type trunk [LSW1-GigabitEthernet0/0/1]port trunk allow-pass vlan 10 20 [LSW1-GigabitEthernet0/0/1]in…...
自定义类型-结构体,联合体和枚举-C语言
引言 能看到结构体,说明C语言想必学习的时间也不少了,在之前肯定也学习过基本数据类型,包括整型int,浮点型float等等。可是在日常生活中,想要描述一个事物并没有那么简单。比如,你要描述一本书,…...
Windows 安装redis,设置开机自启动
Windows 安装redis,设置开机自启动 文章目录 Windows 安装redis,设置开机自启动下载, 解压到指定目录设置redis密码启动redis服务端停止redis服务端设置自启动 下载, 解压到指定目录 官网地址: https://redis.io/ 安装包下载地址: https://github.com/tporadowski/redis/relea…...
Windows安装Mysql Workbench及常用操作
Mysql Workbench是mysql自带的可视化操作界面,功能是强大的,但界面和navicat比,就是觉得别扭,但其实用惯了也还好,各有特色吧。这里记录一下常用的操作。 官方手册:MySQL Workbench 一、安装 1. 下载 官方…...
【计算机网络】15、NAT、NAPT 网络地址转换、打洞
文章目录 一、概念二、分类(主要是传统 NAT)2.1 基本 NAT2.2 NAPT 三、访问NAT下的内网设备的方式3.1 多拨3.2 端口转发、DMZ3.3 UPnP IGD、NAT-PMP3.4 服务器中转:frp 内网穿透3.4.1 NAT 打洞3.4.2 NAT 类型与打洞成功率3.4.2.1 完全圆锥形 …...
【送书活动三期】解决docker服务假死问题
工作中使用docker-compose部署容器,有时候会出现使用docker-compose stop或docker-compose down命令想停掉容器,但是依然无法停止或者一直卡顿在停止中的阶段,这种问题很让人头疼啊! 目录 问题描述问题排查问题解决终极杀招-最粗暴…...
【每日一题】拼车+【差分数组】
文章目录 Tag题目来源解题思路方法一:差分 写在最后 Tag 【差分数组】【数组】【2023-12-02】 题目来源 1094. 拼车 解题思路 本题朴素的解题思路是统计题目中提到的每一个站点的车上人数,如果某个站点的车上人数大于车上的座位数直接返回 false&…...
【开源】基于JAVA的农村物流配送系统
项目编号: S 024 ,文末获取源码。 \color{red}{项目编号:S024,文末获取源码。} 项目编号:S024,文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 系统登录、注册界面2.2 系统功能2.2…...
7、Jenkins+Nexus3+Docker+K8s实现CICD
文章目录 基本环境配置一、Jenkins安装必要插件二、Jenkins系统配置三、新建流水线四、在项目工程里添加Jenkinsfile、deploy.yml五、在项目工程里添加Dockerfile在这里插入图片描述 总结 提示:本章主要记录各基本环境搭建好后如何配置Jenkins流水线部署微服务到K8s…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
五、jmeter脚本参数化
目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...
基于 HTTP 的单向流式通信协议SSE详解
SSE(Server-Sent Events)详解 🧠 什么是 SSE? SSE(Server-Sent Events) 是 HTML5 标准中定义的一种通信机制,它允许服务器主动将事件推送给客户端(浏览器)。与传统的 H…...
Python爬虫(52)Scrapy-Redis分布式爬虫架构实战:IP代理池深度集成与跨地域数据采集
目录 一、引言:当爬虫遭遇"地域封锁"二、背景解析:分布式爬虫的两大技术挑战1. 传统Scrapy架构的局限性2. 地域限制的三种典型表现 三、架构设计:Scrapy-Redis 代理池的协同机制1. 分布式架构拓扑图2. 核心组件协同流程 四、技术实…...
前端打包工具简单介绍
前端打包工具简单介绍 一、Webpack 架构与插件机制 1. Webpack 架构核心组成 Entry(入口) 指定应用的起点文件,比如 src/index.js。 Module(模块) Webpack 把项目当作模块图,模块可以是 JS、CSS、图片等…...
