当前位置: 首页 > 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;…...

TranslucentTB启动失败解决方案:3种方法修复Microsoft.UI.Xaml.2.8缺失问题

TranslucentTB启动失败解决方案&#xff1a;3种方法修复Microsoft.UI.Xaml.2.8缺失问题 【免费下载链接】TranslucentTB A lightweight utility that makes the Windows taskbar translucent/transparent. 项目地址: https://gitcode.com/gh_mirrors/tr/TranslucentTB T…...

一文搞懂训练大模型的数据怎么准备!

谈到大模型&#xff0c;很多人第一反应都是模型参数大、算力强&#xff0c;但其实数据才是大模型真正的底座。没有足够大、足够干净的数据&#xff0c;再先进的模型也发挥不出威力。今天就从数据层面&#xff0c;把大模型训练的几个关键环节梳理清楚。 数据采集与清洗 大模型训…...

告别Keil!用VSCode+EIDE插件打造你的STM32开发环境(附ST-LINK V2避坑指南)

从Keil到VSCode&#xff1a;打造高效STM32开发环境的完整指南 在嵌入式开发领域&#xff0c;Keil MDK长期以来一直是STM32开发的主流工具&#xff0c;但它的封闭性、高昂的授权费用和略显陈旧的用户界面让越来越多的开发者开始寻找替代方案。Visual Studio Code&#xff08;VSC…...

快充、便携、安全兼备,Anker能量盒到底香不香?

随着无线互联网时代的到来&#xff0c;移动设备的续航问题成为人们的新烦恼。无论是频繁出差、旅行&#xff0c;还是移动办公&#xff0c;充电宝几乎已经成为随身必备的装备。 然而&#xff0c;传统充电宝往往存在充电速度慢、体积笨重、功能单一&#xff0c;甚至安全认证不完善…...

Periphery终极部署指南:Docker和Bazel构建的完整说明

Periphery终极部署指南&#xff1a;Docker和Bazel构建的完整说明 【免费下载链接】periphery A tool to identify unused code in Swift projects. 项目地址: https://gitcode.com/gh_mirrors/pe/periphery Periphery是一款强大的Swift代码分析工具&#xff0c;专门用于…...

从EWA Splatting到3DGS:一阶泰勒展开如何保住高斯的“椭圆”形状?

从EWA Splatting到3DGS&#xff1a;一阶泰勒展开如何保住高斯的“椭圆”形状&#xff1f; 在计算机图形学的演进历程中&#xff0c;三维高斯分布&#xff08;3D Gaussian&#xff09;的投影问题一直是个既基础又关键的挑战。想象一下&#xff0c;当你试图将一个完美的三维椭球投…...

道心网络安全学习笔记系列之好靶场的信息收集2

上节课找了一个图片的网址&#xff0c;继续挑战其它靶场&#xff0c;我们看下一题收集十个百度域名&#xff0c;这还不是顺手就来&#xff0c;但是贴吧不行&#xff0c;那还不简单&#xff0c;去访问百度网站&#xff0c;顺便输入一个搜索词&#xff0c;都不用看&#xff0c;前…...

职场“对错陷阱“:为什么你越是讲理,领导越不待见你?

导语&#xff1a;小时候老师教我们"明辨是非"&#xff0c;长大后却发现——在职场里太较真的人&#xff0c;往往混得最差。一、拍桌子的代价2023年春天&#xff0c;我亲眼看见林哥在会议室拍了桌子。"这需求根本不合理&#xff01;数据库设计违反第三范式&#…...

3步搞定ViGEmBus:Windows虚拟游戏手柄驱动终极指南 [特殊字符]

3步搞定ViGEmBus&#xff1a;Windows虚拟游戏手柄驱动终极指南 &#x1f3ae; 【免费下载链接】ViGEmBus Windows kernel-mode driver emulating well-known USB game controllers. 项目地址: https://gitcode.com/gh_mirrors/vi/ViGEmBus 想要在Windows上体验更丰富的游…...

三步修复Windows安全防护:零基础系统工具恢复指南

三步修复Windows安全防护&#xff1a;零基础系统工具恢复指南 【免费下载链接】windows-defender-remover A tool which is uses to remove Windows Defender in Windows 8.x, Windows 10 (every version) and Windows 11. 项目地址: https://gitcode.com/gh_mirrors/wi/wind…...