【设计】855. 考场就座
855. 考场就座
这段代码实现了一个考场安排座位的算法。在这个算法中,考场被模拟成一个从0到n-1的数轴,其中每个位置代表一个座位。目的是在每次学生入座时,找到一个使得所有学生之间距离最大化的座位,并在学生离开时更新座位信息。下面是具体的实现思路和算法描述:
-
初始化 (
public ExamRoom(int n)):n:考场座位的总数。intervals:一个TreeSet,用于存储当前所有空闲区间,并按照某种规则排序。这里的排序规则首先比较两个区间可坐的最远距离,如果相同,则比较区间的末端位置。startToInterval和endToInterval:两个HashMap,分别用于快速定位一个区间的开始和结束位置对应的区间对象。- 在初始化时,会添加一个特殊区间
[-1, n]到intervals中,表示整个考场最开始时全部为空。
-
入座 (
public int seat()):- 从
intervals中取出最优区间(即开始时的排序规则确定的第一个区间),然后根据该区间的起始位置和结束位置计算出新的座位位置。 - 如果该区间的起始位置是-1,说明最左侧是空的,因此新的座位位置是0。
- 如果该区间的结束位置是
n,说明最右侧是空的,因此新的座位位置是n-1。 - 否则,新的座位位置是区间中点。
- 入座后,将原区间分为两个新区间,并加入到
intervals中。
- 从
-
离开 (
public void leave(int p)):- 当一个学生离开座位时,通过
endToInterval和startToInterval找到该座位所属的两个区间。 - 将这两个区间合并为一个新区间,并更新到
intervals中。
- 当一个学生离开座位时,通过
-
辅助方法:
private void removeInterval(int[] interval):从intervals、startToInterval和endToInterval中移除指定区间。private void addInterval(int[] interval):向intervals、startToInterval和endToInterval中添加新区间。private int dist(int[] interval):计算一个区间中可以坐的最远距离。如果区间的起始或结束是边界,距离计算方式略有不同。
通过上述方法,该算法能够有效地在每次学生入座时找到最优的座位,并在学生离开时更新座位信息,以保证考场的座位安排尽可能地公平和高效。
class ExamRoom {int n;TreeSet<int[]> intervals;HashMap<Integer, int[]> startToInterval;HashMap<Integer, int[]> endToInterval;public ExamRoom(int n) {this.n = n;startToInterval = new HashMap<>();endToInterval = new HashMap<>();intervals = new TreeSet<>((a, b) ->dist(b) != dist(a) ? dist(b) - dist(a) : a[1] - b[1]);addInterval(new int[]{-1, n});}public int seat() {int[] interval = intervals.pollFirst();int start = interval[0];int end = interval[1];int seat = 0;if (start == -1) {seat = 0;} else if (end == n) {seat = n - 1;} else {seat = (start + end) >>> 1;}addInterval(new int[]{start, seat});addInterval(new int[]{seat, end});return seat;}public void leave(int p) {int[] i1 = endToInterval.get(p);int[] i2 = startToInterval.get(p);int start = i1[0];int end = i2[1];int[] interval = new int[]{start, end};removeInterval(i1);removeInterval(i2);addInterval(interval);}private void removeInterval(int[] interval) {intervals.remove(interval);startToInterval.remove(interval[0]);endToInterval.remove(interval[1]);}private void addInterval(int[] interval) {intervals.add(interval);startToInterval.put(interval[0], interval);endToInterval.put(interval[1], interval);}private int dist(int[] interval) {int start = interval[0];int end = interval[1];if (start == -1 || end == n) {return end - start - 1;}return (end - start) / 2;}
}/*** Your ExamRoom object will be instantiated and called as such:* ExamRoom obj = new ExamRoom(n);* int param_1 = obj.seat();* obj.leave(p);*/相关文章:
【设计】855. 考场就座
855. 考场就座 这段代码实现了一个考场安排座位的算法。在这个算法中,考场被模拟成一个从0到n-1的数轴,其中每个位置代表一个座位。目的是在每次学生入座时,找到一个使得所有学生之间距离最大化的座位,并在学生离开时更新座位信息…...
Android中的传感器类型和接口名称
本文将介绍传感器坐标轴、基础传感器和复合传感器(动作传感器、姿势传感器、未校准传感器和互动传感器)。 1. 传感器坐标轴 许多传感器的传感器事件值在相对于设备静止的特定坐标系中表示。 1.1 移动设备坐标轴 Sensor API 仅与屏幕的自然方向相关&a…...
解析进程 /proc/pid/maps 和 /proc/pid/smaps
目录 /proc//maps 背景 具体描述 代码实现 实践 /proc/pid/smaps smaps各子项详解 代码实现 代码调用的路径如下: 小结 /proc/<pid>/maps 背景 相对于/proc/meminfo和dumpsys meminfo可以看到系统整体的内存信息,我们还需要能够具体到…...
【MQ】消息队列概述
📝个人主页:五敷有你 🔥系列专栏:MQ ⛺️稳中求进,晒太阳 定义 消息队列:一般我们简称为MQ(Message Queue) Message Queue :消息队列中间件,很多初学者认为,MQ通过消息的发送…...
交友盲盒系统PHP开源的盲盒源码
源码介绍: 交友盲盒系统是一款基于PHP开发的开源免费盲盒系统,旨在为用户提供一个充满乐趣和惊喜的社交体验。该系统具有丰富的功能和灵活的扩展性,可以轻松地满足各种线上交友、抽奖活动等场景的需求。 安装说明: PHP版本&…...
【Flutter 面试题】什么是异步编程 Flutter中如何处理异步操作?
【Flutter 面试题】什么是异步编程 Flutter中如何处理异步操作? 文章目录 写在前面解答补充说明从网络API异步获取数据并解析 写在前面 关于我 ,小雨青年 👉 CSDN博客专家,GitChat专栏作者,阿里云社区专家博主&#x…...
处理error: remote origin already exists.及其Gitee文件上传保姆级教程
解决error: remote origin already exists.: 删除远程 Git 仓库 git remote rm origin 再添加远程 Git 仓库 git remote add origin (HTTPS) 比如这样: 然后再push过去就ok了 好多人可能还是不熟悉怎么将文件上传 Gitee:我…...
网络编程套接字(2)——Socket套接字
目录 一、概念 二、分类 1、流套接字(使用传输层TCP协议) TCP的特点 2、数据报套接字(使用传输层UDP协议) UDP的特点 3、原始套接字 一、概念 Socket套接字,是由系统提供用于网络通信的技术,是基于T…...
向量错题本
《1800》 1 看变换求和能不能成为0,为0,就是线性相关 2 矩阵等价 3 4<...
FPGA-VGA成像原理与时序
什么是VGA: VGA, Video Graphics Array。即视频图形阵列,具有分辨率高、显示速率快、颜色丰富等优点。VGA接口不但是CRT显示设备的标准接口,同样也是LCD液晶显示设备的标准接口,具有广泛的应用范围。在FGPA中,常广泛用于图像处理等领域。 VGA 显示器成像原理 在 VGA 标准刚兴…...
【VTKExamples::Points】第三期 ExtractClusters
很高兴在雪易的CSDN遇见你 VTK技术爱好者 QQ:870202403 公众号:VTK忠粉 前言 本文分享VTK样例ExtractClusters,并解析接口vtkEuclideanClusterExtraction,希望对各位小伙伴有所帮助! 感谢各位小伙伴的点赞+关注,小易会继续努力分享,一起进步! 你的点赞就是我…...
迅速上手:CentOS 系统下 SSH 服务配置指南
前言 掌握 SSH 服务,就像拥有了一把解锁网络世界的钥匙。本文深入浅出地介绍了如何使用 SSH(Secure Shell)服务,从连接远程服务器到安全文件传输,让你轻松驾驭远程管理与数据传输,提高工作效率,…...
day38 动态规划part1
509. 斐波那契数 简单 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) 0,F(1) 1 F(n) F(n - 1) F(n - 2),…...
01背包问题 刷题笔记
思路 dp 用f[i][j]来表示当体积为j时 考虑前i件物品可以获得的 最大值 记住f[i][j]本身是个价“价值” 考虑两种状态 是否将第i件物品放入背包里面 将背包的体积从小到大递增来进行考虑 首先 考虑条件 如果当前增加的体积放不下下一件物品 则该体积 可以获得的最大值可以直接…...
docker安装包(Linux和windows)
Linux——docker-20.10.9.tgz 网盘地址:链接:https://pan.baidu.com/s/1T3qfVZ-uT-vMAo8w6heTMw 提取码:qu85 windows——docker19.03.1 链接:https://pan.baidu.com/s/1mK6hqhkGCBs6tdBHJxrdPw 提取码:4dkj...
RabbitMQ 安装使用
文章目录 RabbitMQ 安装使用安装下载 Erlang下载 RabbitMQ 的服务安装好后看是否有 RabbitMQ 的服务开启管理 UIRabbitMQ 端口使用一览图 使用输出最简单的 Hello World!生产者定义消费者消费消息小拓展 RabbitMQ 安装使用 安装 下载 Erlang RabbitMQ 是用这个语…...
echarts x轴名称过长tip显示全称
xAxis的axisLabel的内容如下: axisLabel: { rotate: -45, color: document.body.className.indexOf(custom-f4c46d) > -1 ? #fff : #343434, // 显示省略号操作(第一步) formatter: function (value) { var val if (value.length >…...
js和css阻塞问题
面试常见问题 css 加载会不会阻塞 js 的加载?(不会)css 加载会不会阻塞 js 的执行?(会)css 加载会不会阻塞 DOM 的解析?(不会)css 加载会不会阻塞 DOM 的渲染࿱…...
MySQL 的基础操作
数据库的基础操作 1. 库操作2. 表的操作3. 数据类型 数据库是现代应用程序中至关重要的组成部分,通过数据库管理系统(DBMS)存储和管理数据。 1. 库操作 创建数据库 创建数据库是开始使用数据库的第一步。下面是一些常见的创建数据库的示例&a…...
【python进阶篇】面向对象编程(1)
面向对象编程——Object Oriented Programming,简称OOP,是一种程序设计思想。OOP把对象作为程序的基本单元,一个对象包含了数据和操作数据的函数。 在Python中,所有数据类型都可以视为对象,当然也可以自定义对象。自定…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
