当前位置: 首页 > news >正文

Leetcode 3440. Reschedule Meetings for Maximum Free Time II

  • Leetcode 3440. Reschedule Meetings for Maximum Free Time II
    • 1. 解题思路
    • 2. 代码实现
  • 题目链接:3440. Reschedule Meetings for Maximum Free Time II

1. 解题思路

这一题某种意义上来说甚至是上一题Leetcode 3439的简化版本(关于这一题的解答可以参考拙作Leetcode 3439. Reschedule Meetings for Maximum Free Time I),因为只要求 k = 1 k=1 k=1,但是差别在于可以改变会议的开始顺序。

因此,我们虽然不需要考察连续 k k k个会议的持续时间,但是需要考察一下在其他会议的间隔范围内是否存在某个gap大于当前会议的时间,如果存在的话我们就可以直接把该会议挪过去,这样就可以直接获取整段的自由时间了。

综上,这一题和上一题基本实现思路就完全一致,唯一的差别就在于需要多求一个其他会议区间内的最大gap时间,这个我们可以通过一个segment tree来实现,对应的内容网上有很多,我自己也有一篇博客作为备忘(经典算法:Segment Tree),因此这里就不过多展开了,有兴趣的读者可以移步去看看。

2. 代码实现

给出python代码实现如下:

class SegmentTree:def __init__(self, arr):self.length = len(arr)self.tree = self.build(arr)def feature_func(self, *args):return max(args)def build(self, arr):n = len(arr)tree = [0 for _ in range(2*n)]for i in range(n):tree[i+n] = arr[i]for i in range(n-1, 0, -1):tree[i] = self.feature_func(tree[i<<1], tree[(i<<1) | 1])return treedef update(self, idx, val):idx = idx + self.lengthself.tree[idx] = valwhile idx > 1:self.tree[idx>>1] = self.feature_func(self.tree[idx], self.tree[idx ^ 1])idx = idx>>1returndef query(self, lb, rb):if rb < lb:return 0lb += self.length rb += self.lengthnodes = []while lb < rb:if lb & 1 == 1:nodes.append(self.tree[lb])lb += 1if rb & 1 == 0:nodes.append(self.tree[rb])rb -= 1lb = lb >> 1rb = rb >> 1if lb == rb:nodes.append(self.tree[rb])return self.feature_func(*nodes)class Solution:def maxFreeTime(self, eventTime: int, startTime: List[int], endTime: List[int]) -> int:meetings = [(i, j, j-i) for i, j in zip(startTime, endTime)]n = len(meetings)freeTimes = [meetings[0][0]] + [meetings[i+1][0] - meetings[i][1] for i in range(n-1)] + [eventTime - meetings[-1][1]]ans = max(freeTimes)segment_tree = SegmentTree(freeTimes)durations = list(accumulate([x[2] for x in meetings], initial=0))for i in range(n):if i == 0:tot = meetings[i+1][0]elif i+1 == n:tot = eventTime - meetings[i-1][1]else:tot = meetings[i+1][0] - meetings[i-1][1]d = durations[i+1] - durations[i]gap = max(segment_tree.query(0, i-1), segment_tree.query(i+2, n))if d > gap:ans = max(ans, tot-d)else:ans = max(ans, tot)return ans

提交代码评测得到:耗时2361ms,占用内存51.1MB。

相关文章:

Leetcode 3440. Reschedule Meetings for Maximum Free Time II

Leetcode 3440. Reschedule Meetings for Maximum Free Time II 1. 解题思路2. 代码实现 题目链接&#xff1a;3440. Reschedule Meetings for Maximum Free Time II 1. 解题思路 这一题某种意义上来说甚至是上一题Leetcode 3439的简化版本&#xff08;关于这一题的解答可以…...

专门记录台式电脑常见问题

1、蓝屏死机&#xff0c;检查内存硬盘和cpu 2、拆内存条&#xff0c;用橡皮擦金手指 3、放主板静电&#xff0c;扣主板电池 4、系统时间不正确&#xff0c;主板电池没电 5、开机键坏了 6、电脑主机的风扇转&#xff0c;正常通电运行&#xff0c;但显示器没信号。看键盘的num键&…...

[操作系统] 进程终止

在计算机操作系统中&#xff0c;进程&#xff08;Process&#xff09;是程序在运行中的实例&#xff0c;而进程的生命周期始于创建&#xff0c;终于终止。进程终止不仅仅意味着程序执行结束&#xff0c;还涉及资源的回收、状态的传递、以及可能的错误处理。在 Linux 和 Unix 系…...

[x86 ubuntu22.04]进入S4失败

目录 1 问题描述 2 解决过程 2.1 查看内核日志 2.2 新建一个交换分区 2.3 指定交换分区的位置 1 问题描述 CPU&#xff1a;G6900E OS&#xff1a;ubuntu22.04 Kernel&#xff1a;6.8.0-49-generic 使用“echo disk > /sys/power/state”命令进入 S4&#xff0c;但是无法…...

12.外观模式(Facade Pattern)

定义 外观模式&#xff08;Facade Pattern&#xff09; 是一种结构型设计模式&#xff0c;它通过为复杂的子系统提供一个统一的接口&#xff0c;使得子系统的使用更加简化。外观模式通常隐藏了复杂的内部子系统&#xff0c;使得客户端可以通过一个简单的接口与这些子系统进行交…...

ES6 入门教程:箭头函数、解构赋值及其他新特性详解

ES6 入门教程&#xff1a;箭头函数、解构赋值及其他新特性详解 ES6 入门教程&#xff1a;箭头函数、解构赋值及其他新特性详解引言什么是 ES6&#xff1f;箭头函数&#xff08;Arrow Functions&#xff09;1. 基本语法2. 常见特点&#xff08;1&#xff09;没有自己的 this 上下…...

win编译openssl

一、perl执行脚本 1、安装perl脚本 perl安装 2、配置perl脚本 perl Configure VC-WIN32 no-asm no-shared --prefixE:\openssl-x.x.x\install二、编译openssl 1、使用vs工具编译nmake 如果使用命令行nmake编译会提示“无法打开包括文件: “limits.h”“ 等错误信息 所以…...

51单片机看门狗系统

在 STC89C52 单片机中&#xff0c;看门狗控制寄存器的固定地址为 0xE1。此地址由芯片厂商在硬件设计时确定&#xff0c;但是它在头文件中并未给出&#xff0c;因此在使用看门狗系统时需要声明下这个特殊功能寄存器 sfr WDT_CONTR 0xE1; 本案将用一个小灯的工作状况来展示看门…...

探索 paraphrase-MiniLM-L6-v2 模型在自然语言处理中的应用

在自然语言处理&#xff08;NLP&#xff09;领域&#xff0c;将文本数据转换为机器学习模型可以处理的格式是至关重要的。近年来&#xff0c;sentence-transformers 库因其在文本嵌入方面的卓越表现而受到广泛关注。本文将深入探讨 paraphrase-MiniLM-L6-v2 模型&#xff0c;这…...

2025最新软件测试面试大全(附答案+文档)

&#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 1、问&#xff1a;你在测试中发现了一个bug&#xff0c;但是开发经理认为这不是一个bug&#xff0c;你应该怎样解决? 首先&#xff0c;将问题提交到缺陷管理库里…...

Java语法进阶

目录&#xff1a; Object类、常用APICollection、泛型List、Set、数据结构、CollectionsMap与斗地主案例异常、线程线程、同步等待与唤醒案例、线程池、Lambda表达式File类、递归字节流、字符流缓冲流、转换流、序列化流、Files网络编程 十二、函数式接口Stream流、方法引用 一…...

UNI-MOL: A UNIVERSAL 3D MOLECULAR REPRESENTATION LEARNING FRAMEWORK

UNI-MOL: A UNIVERSAL 3D MOLECULAR REPRESENTATION LEARNING FRAMEWORK Neurips23 推荐指数&#xff1a;#paper/⭐⭐⭐#​&#xff08;工作量不小) 动机 在大多数分子表征学习方法中&#xff0c;分子被视为 1D 顺序标记或2D 拓扑图&#xff0c;这限制了它们为下游任务整合…...

笔记day7

文章目录 1 分页功能实现2 分页器的展示需要哪些数据&#xff08;条件&#xff09;&#xff1f;3 自定义分页器4 分页器存在问题5 分页器动态展示6 开发某一个商品的详情页面 1 分页功能实现 为什么很多项目采用分页功能&#xff0c;比如电商平台同时展示的数据有很多&#xf…...

106,【6】 buuctf web [SUCTF 2019]CheckIn

进入靶场 文件上传 老规矩&#xff0c;桌面有啥传啥 过滤了<? 寻找不含<?的一句话木马 文件名 123(2).php.jpg 文件内容 GIF89a? <script language"php">eval($_GET[123]);</script> 123即密码&#xff0c;可凭借个人喜好更换 再上传一个文…...

基于Ubuntu2404搭建Zabbix7.2

Zabbix 搭建zabbix zabbix7.2已推出&#xff1a;官网 增加的新功能如下&#xff1a; 1.使用新的热门商品小部件全面概览指标 数据概览小部件已转换为热门项目小部件使用项目模式可以实现细粒度的项目选择利用条形图、指标和迷你图来可视化您的数据定义价值阈值以动态地可视化…...

OPENGLPG第九版学习 - 着色器基础

文章目录 2.1 着色器与OpenGL2.2 0penGL的可编程管线2.3 OpenGL着色语言GLSL概述2.3.1 使用GLSL构建着色器变量的声明变量的作用域变量的初始化构造函数 、 类型转换聚合类型访问向量和矩阵中的元素结构体数组多维数组 2.3.2 存储限制符const 存储限制符in 存储限制符out 存储限…...

Android 使用ExpandableListView时,需要注意哪些细节

1. 布局属性设置 尺寸属性 宽度和高度&#xff1a;要合理设置 android:layout_width 和 android:layout_height 属性。如果设置为 match_parent&#xff0c;它会填满父容器&#xff1b;设置为 wrap_content&#xff0c;则会根据内容自动调整大小。例如&#xff0c;若想让 Exp…...

redis简介及应用

文章目录 1.redis简介2.安装配置2.1 单机部署2.2 配置 3 主从部署4 哨兵部署5.集群部署6.客户端工具 1.redis简介 某些网站出现的问题&#xff0c;如12306、淘宝等… 2.安装配置 2.1 单机部署 安装gcc、关闭防火墙、关闭selinux等 #安装gcc yum -y install gcc #关闭防火墙…...

Electron使用WebAssembly实现CRC-8 MAXIM校验

Electron使用WebAssembly实现CRC-8 MAXIM校验 将C/C语言代码&#xff0c;经由WebAssembly编译为库函数&#xff0c;可以在JS语言环境进行调用。这里介绍在Electron工具环境使用WebAssembly调用CRC-8 MAXIM格式校验的方式。 CRC-8 MAXIM校验函数WebAssembly源文件 C语言实现C…...

人工智能赋能企业系统架构设计:以ERP与CRM系统为例

一、引言 1.1 研究背景与意义 在数字化时代&#xff0c;信息技术飞速发展&#xff0c;人工智能&#xff08;Artificial Intelligence, AI&#xff09;作为一项具有变革性的技术&#xff0c;正深刻地影响着各个领域。近年来&#xff0c;AI 在技术上取得了显著突破&#xff0c;…...

单片机开发三大软件架构对比与实践

单片机开发常用软件架构深度解析1. 项目概述在嵌入式系统开发中&#xff0c;软件架构设计直接影响系统的可靠性、可维护性和实时性。本文系统分析三种主流单片机软件架构方案&#xff0c;包括时间片轮询法、操作系统方案和前后台顺序执行法&#xff0c;为开发者提供架构选型参考…...

Windows 内网 Web 服务穿透方案推荐

Windows 内网 Web 服务穿透方案推荐 面向场景&#xff1a;内网机器为 Windows&#xff0c;需从公网或外网访问内网 HTTP/HTTPS Web 服务&#xff1b;优先选择相对不易被误报、来源清晰、可审计的方案。 关于「报毒」的说明 穿透类软件常被启发式引擎标为「风险/可疑」&#xf…...

VSCode党必看!用轻量级方案玩转LaTeX:2024年TexLive+VSCode配置全攻略

VSCode党必看&#xff01;用轻量级方案玩转LaTeX&#xff1a;2024年TexLiveVSCode配置全攻略 对于习惯在VSCode中高效编码的开发者而言&#xff0c;切换到传统LaTeX编辑器往往意味着要放弃熟悉的快捷键、扩展生态和流畅的代码体验。本文将带你用完全基于VSCode的轻量级方案构建…...

知识引导上下文优化(KgCoOp):一种解决灾难性遗忘的 Prompt Tuning 机制

来源&#xff1a;DeepHub IMBA 本文约3000字&#xff0c;建议阅读5分钟本文提出了一种简单有效的约束机制。视觉-语言模型&#xff08;VLMs&#xff09;如 CLIP 彻底改变了零样本图像识别的处理方式。这类模型在包含 4 亿个图像-文本对的大规模数据集上进行训练&#xff0c;捕获…...

说说你对spring的IOC的理解

面试 IOC指的就是控制反转&#xff0c;指的就是创建对象的控制权的转移&#xff0c;简单来说&#xff0c;由之前的手动new对象&#xff0c;转换成了由spring自动生产&#xff0c;spring利用java的反射机制&#xff0c;根据配置文件或注解在运行时动态创建并管理对象。...

计算机毕业设计springboot基于的游戏交易平台 基于SpringBoot的虚拟资产流通服务平台的设计与实现 基于SpringBoot架构的网络游戏账号及道具交易系统的设计与实现

计算机毕业设计springboot基于的游戏交易平台&#xff08;配套有源码 程序 mysql数据库 论文&#xff09; 本套源码可以在文本联xi,先看具体系统功能演示视频领取&#xff0c;可分享源码参考。随着互联网技术的飞速发展和网络游戏产业的蓬勃兴起&#xff0c;虚拟资产交易已成为…...

vs code 实现source insight中的快捷键功能

1.自定义快捷键连续两组快捷键CtrlK CtrlS打开键盘快捷键定义界面修改向前向后的快捷键。ctrlu删除当前行复制当前行到下面2.增加bookmarks功能扩展部分装插件&#xff0c;定义快捷键ctrlm增加标签可以修改标签3.多行移动多行向上移动&#xff0c;向下移动Windows/Linux 用 Alt…...

BLE5.1 与蓝牙Mesh 在手环数字车钥匙中的角色与体验升级

可穿戴数字车钥匙把传统实体钥匙的能力收敛到手环、手表等贴身设备上&#xff0c;通过近距无线链路与车载控制器或专用通信单元交互&#xff0c;支持解闭锁、启动、迎宾等操作。典型实现会组合 低功耗蓝牙&#xff08;BLE&#xff09; 做常在线链路与距离感知&#xff0c;并以 …...

一种路径优化和速度优化算法实现(仿照百度Apollo方案),只提供代码,有相关的readme文...

一种路径优化和速度优化算法实现&#xff08;仿照百度Apollo方案&#xff09;&#xff0c;只提供代码&#xff0c;有相关的readme文件。 自动驾驶 &#xff0c;路径优化&#xff0c;速度优化&#xff0c;pnc。 的代码最近在折腾自动驾驶的路径规划模块&#xff0c;发现实际落地…...

Unity游戏开发:A*寻路算法实战,5步搞定NPC智能移动(附完整Demo)

Unity游戏开发&#xff1a;A*寻路算法实战指南与高级优化技巧 在游戏开发中&#xff0c;NPC的智能移动一直是开发者需要解决的核心问题之一。想象一下&#xff0c;当玩家在《魔兽世界》中穿越荆棘谷时&#xff0c;那些巡逻的巨魔守卫是如何绕过树木和山丘找到最短路径的&#x…...