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

【设计】855. 考场就座

855. 考场就座

这段代码实现了一个考场安排座位的算法。在这个算法中,考场被模拟成一个从0到n-1的数轴,其中每个位置代表一个座位。目的是在每次学生入座时,找到一个使得所有学生之间距离最大化的座位,并在学生离开时更新座位信息。下面是具体的实现思路和算法描述:

  1. 初始化 (public ExamRoom(int n)):

    • n:考场座位的总数。
    • intervals:一个TreeSet,用于存储当前所有空闲区间,并按照某种规则排序。这里的排序规则首先比较两个区间可坐的最远距离,如果相同,则比较区间的末端位置。
    • startToIntervalendToInterval:两个HashMap,分别用于快速定位一个区间的开始和结束位置对应的区间对象。
    • 在初始化时,会添加一个特殊区间[-1, n]intervals中,表示整个考场最开始时全部为空。
  2. 入座 (public int seat()):

    • intervals中取出最优区间(即开始时的排序规则确定的第一个区间),然后根据该区间的起始位置和结束位置计算出新的座位位置。
    • 如果该区间的起始位置是-1,说明最左侧是空的,因此新的座位位置是0。
    • 如果该区间的结束位置是n,说明最右侧是空的,因此新的座位位置是n-1
    • 否则,新的座位位置是区间中点。
    • 入座后,将原区间分为两个新区间,并加入到intervals中。
  3. 离开 (public void leave(int p)):

    • 当一个学生离开座位时,通过endToIntervalstartToInterval找到该座位所属的两个区间。
    • 将这两个区间合并为一个新区间,并更新到intervals中。
  4. 辅助方法:

    • private void removeInterval(int[] interval):从intervalsstartToIntervalendToInterval中移除指定区间。
    • private void addInterval(int[] interval):向intervalsstartToIntervalendToInterval中添加新区间。
    • 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. 考场就座 这段代码实现了一个考场安排座位的算法。在这个算法中&#xff0c;考场被模拟成一个从0到n-1的数轴&#xff0c;其中每个位置代表一个座位。目的是在每次学生入座时&#xff0c;找到一个使得所有学生之间距离最大化的座位&#xff0c;并在学生离开时更新座位信息…...

Android中的传感器类型和接口名称

本文将介绍传感器坐标轴、基础传感器和复合传感器&#xff08;动作传感器、姿势传感器、未校准传感器和互动传感器&#xff09;。 1. 传感器坐标轴 许多传感器的传感器事件值在相对于设备静止的特定坐标系中表示。 1.1 移动设备坐标轴 Sensor API 仅与屏幕的自然方向相关&a…...

解析进程 /proc/pid/maps 和 /proc/pid/smaps

目录 /proc//maps 背景 具体描述 代码实现 实践 /proc/pid/smaps smaps各子项详解 代码实现 代码调用的路径如下&#xff1a; 小结 /proc/<pid>/maps 背景 相对于/proc/meminfo和dumpsys meminfo可以看到系统整体的内存信息&#xff0c;我们还需要能够具体到…...

【MQ】消息队列概述

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;MQ ⛺️稳中求进&#xff0c;晒太阳 定义 消息队列&#xff1a;一般我们简称为MQ(Message Queue) Message Queue :消息队列中间件&#xff0c;很多初学者认为&#xff0c;MQ通过消息的发送…...

交友盲盒系统PHP开源的盲盒源码

源码介绍&#xff1a; 交友盲盒系统是一款基于PHP开发的开源免费盲盒系统&#xff0c;旨在为用户提供一个充满乐趣和惊喜的社交体验。该系统具有丰富的功能和灵活的扩展性&#xff0c;可以轻松地满足各种线上交友、抽奖活动等场景的需求。 安装说明&#xff1a; PHP版本&…...

【Flutter 面试题】什么是异步编程 Flutter中如何处理异步操作?

【Flutter 面试题】什么是异步编程 Flutter中如何处理异步操作&#xff1f; 文章目录 写在前面解答补充说明从网络API异步获取数据并解析 写在前面 关于我 &#xff0c;小雨青年 &#x1f449; CSDN博客专家&#xff0c;GitChat专栏作者&#xff0c;阿里云社区专家博主&#x…...

处理error: remote origin already exists.及其Gitee文件上传保姆级教程

解决error: remote origin already exists.&#xff1a; 删除远程 Git 仓库 git remote rm origin 再添加远程 Git 仓库 git remote add origin &#xff08;HTTPS&#xff09; 比如这样&#xff1a; 然后再push过去就ok了 好多人可能还是不熟悉怎么将文件上传 Gitee:我…...

网络编程套接字(2)——Socket套接字

目录 一、概念 二、分类 1、流套接字&#xff08;使用传输层TCP协议&#xff09; TCP的特点 2、数据报套接字&#xff08;使用传输层UDP协议&#xff09; UDP的特点 3、原始套接字 一、概念 Socket套接字&#xff0c;是由系统提供用于网络通信的技术&#xff0c;是基于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 服务&#xff0c;就像拥有了一把解锁网络世界的钥匙。本文深入浅出地介绍了如何使用 SSH&#xff08;Secure Shell&#xff09;服务&#xff0c;从连接远程服务器到安全文件传输&#xff0c;让你轻松驾驭远程管理与数据传输&#xff0c;提高工作效率&#xff0c…...

day38 动态规划part1

509. 斐波那契数 简单 斐波那契数 &#xff08;通常用 F(n) 表示&#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始&#xff0c;后面的每一项数字都是前面两项数字的和。也就是&#xff1a; F(0) 0&#xff0c;F(1) 1 F(n) F(n - 1) F(n - 2)&#xff0c;…...

01背包问题 刷题笔记

思路 dp 用f[i][j]来表示当体积为j时 考虑前i件物品可以获得的 最大值 记住f[i][j]本身是个价“价值” 考虑两种状态 是否将第i件物品放入背包里面 将背包的体积从小到大递增来进行考虑 首先 考虑条件 如果当前增加的体积放不下下一件物品 则该体积 可以获得的最大值可以直接…...

docker安装包(Linux和windows)

Linux——docker-20.10.9.tgz 网盘地址&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1T3qfVZ-uT-vMAo8w6heTMw 提取码&#xff1a;qu85 windows——docker19.03.1 链接&#xff1a;https://pan.baidu.com/s/1mK6hqhkGCBs6tdBHJxrdPw 提取码&#xff1a;4dkj...

RabbitMQ 安装使用

文章目录 RabbitMQ 安装使用安装下载 Erlang下载 RabbitMQ 的服务安装好后看是否有 RabbitMQ 的服务开启管理 UIRabbitMQ 端口使用一览图 使用输出最简单的 Hello World&#xff01;生产者定义消费者消费消息小拓展 RabbitMQ 安装使用 安装 下载 Erlang RabbitMQ 是用这个语…...

echarts x轴名称过长tip显示全称

xAxis的axisLabel的内容如下&#xff1a; axisLabel: { rotate: -45, color: document.body.className.indexOf(custom-f4c46d) > -1 ? #fff : #343434, // 显示省略号操作&#xff08;第一步&#xff09; formatter: function (value) { var val if (value.length >…...

js和css阻塞问题

面试常见问题 css 加载会不会阻塞 js 的加载&#xff1f;&#xff08;不会&#xff09;css 加载会不会阻塞 js 的执行&#xff1f;&#xff08;会&#xff09;css 加载会不会阻塞 DOM 的解析&#xff1f;&#xff08;不会&#xff09;css 加载会不会阻塞 DOM 的渲染&#xff1…...

MySQL 的基础操作

数据库的基础操作 1. 库操作2. 表的操作3. 数据类型 数据库是现代应用程序中至关重要的组成部分&#xff0c;通过数据库管理系统&#xff08;DBMS&#xff09;存储和管理数据。 1. 库操作 创建数据库 创建数据库是开始使用数据库的第一步。下面是一些常见的创建数据库的示例&a…...

【python进阶篇】面向对象编程(1)

面向对象编程——Object Oriented Programming&#xff0c;简称OOP&#xff0c;是一种程序设计思想。OOP把对象作为程序的基本单元&#xff0c;一个对象包含了数据和操作数据的函数。 在Python中&#xff0c;所有数据类型都可以视为对象&#xff0c;当然也可以自定义对象。自定…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

MySQL:分区的基本使用

目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区&#xff08;Partitioning&#xff09;是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分&#xff08;分区&#xff09;可以独立存储、管理和优化&#xff0c;…...

第八部分:阶段项目 6:构建 React 前端应用

现在&#xff0c;是时候将你学到的 React 基础知识付诸实践&#xff0c;构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段&#xff0c;你可以先使用模拟数据&#xff0c;或者如果你的后端 API&#xff08;阶段项目 5&#xff09;已经搭建好&#xff0c;可以直接连…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究

摘要&#xff1a;在消费市场竞争日益激烈的当下&#xff0c;传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序&#xff0c;探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式&#xff0c;分析沉浸式体验的优势与价值…...

归并排序:分治思想的高效排序

目录 基本原理 流程图解 实现方法 递归实现 非递归实现 演示过程 时间复杂度 基本原理 归并排序(Merge Sort)是一种基于分治思想的排序算法&#xff0c;由约翰冯诺伊曼在1945年提出。其核心思想包括&#xff1a; 分割(Divide)&#xff1a;将待排序数组递归地分成两个子…...

FTXUI::Dom 模块

DOM 模块定义了分层的 FTXUI::Element 树&#xff0c;可用于构建复杂的终端界面&#xff0c;支持响应终端尺寸变化。 namespace ftxui {...// 定义文档 定义布局盒子 Element document vbox({// 设置文本 设置加粗 设置文本颜色text("The window") | bold | color(…...