【康复学习--LeetCode每日一题】3111. 覆盖所有点的最少矩形数目

题目:

给你一个二维整数数组 point ,其中 points[i] = [xi, yi] 表示二维平面内的一个点。同时给你一个整数 w 。你需要用矩形 覆盖所有 点。

每个矩形的左下角在某个点 (x1, 0) 处,且右上角在某个点 (x2, y2) 处,其中 x1 <= x2 且 y2 >= 0 ,同时对于每个矩形都 必须 满足 x2 - x1 <= w 。

如果一个点在矩形内或者在边上,我们说这个点被矩形覆盖了。

请你在确保每个点都 至少 被一个矩形覆盖的前提下,最少 需要多少个矩形。

注意:一个点可以被多个矩形覆盖。

示例 1:
在这里插入图片描述
输入:points = [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]], w = 1
输出:2
解释:
上图展示了一种可行的矩形放置方案:
一个矩形的左下角在 (1, 0) ,右上角在 (2, 8) 。
一个矩形的左下角在 (3, 0) ,右上角在 (4, 8) 。

示例 2:
在这里插入图片描述
输入:points = [[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]], w = 2
输出:3
解释:
上图展示了一种可行的矩形放置方案:
一个矩形的左下角在 (0, 0) ,右上角在 (2, 2) 。
一个矩形的左下角在 (3, 0) ,右上角在 (5, 5) 。
一个矩形的左下角在 (6, 0) ,右上角在 (6, 6) 。

示例 3:
在这里插入图片描述
输入:points = [[2,3],[1,2]], w = 0
输出:2
解释:
上图展示了一种可行的矩形放置方案:
一个矩形的左下角在 (1, 0) ,右上角在 (1, 2) 。
一个矩形的左下角在 (2, 0) ,右上角在 (2, 3) 。

提示:
1 <= points.length <= 105
points[i].length==2
0 <= xi ==points[i][0] <= 109
0 <= yi == points[i][1] <= 109
0 <= w <= 109
所有点坐标 (xi, yi) 互不相同。

思路:

贪心,按横坐标从小打到排序,查看需要多少次能将横坐标全部覆盖,每次和x+w进行比较,x+w内代表都可覆盖,超过此范围的则代表需要一个新矩形。

代码:

class Solution {//贪心 横坐标需要几个矩形可以覆盖public int minRectanglesToCoverPoints(int[][] points, int w) {// 按横坐标从小到大排序Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));int ans = 0;// 每次用x+w来更新边界值int bound = -1;for (int[] p : points) {if (p[0] > bound) {bound = p[0] + w;ans++;}}return ans;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3280332.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

职业教育计算机网络综合实验实训室建设应用案例

近年来&#xff0c;职业教育在培养技能型人才方面发挥着越来越重要的作用。然而&#xff0c;传统的计算机网络技术教学模式往往重理论、轻实践&#xff0c;导致学生缺乏实际操作能力和职业竞争力。为了改变这一现状&#xff0c;唯众结合职业教育特点&#xff0c;提出了“教、学…

04.FreeRTOS任务创建

04. FreeRTOS任务创建与任务删除 1. FreeRTOS创建和删除任务相关API函数 函数描述xTaskCreate()动态方式创建任务xTaskCreateStatic()静态方式创建任务xTaskCreateRestricted()动态方式创建使用 MPU 限制的任务xTaskCreateRestrictedStatic()静态方式创建使用 MPU 限制的任务…

C# Unity 面向对象补全计划 之 继承(字段与属性)

本文仅作学习笔记与交流&#xff0c;不作任何商业用途&#xff0c;作者能力有限&#xff0c;如有不足还请斧正 本系列旨在通过补全学习之后&#xff0c;给出任意类图都能实现并做到逻辑上严丝合缝 Q&#xff1a;为什么要单讲继承字段与属性&#xff0c;不讲继承方法了吗&#x…

Centos 7配置问题

在VMWare12上面安装Centos 7 Linux虚拟机&#xff0c;在切换到命令界面时&#xff0c;需要登录用户名和密码&#xff0c;但发现输入用户后有字符显示&#xff0c;但是密码没有。 经过一系列查看后&#xff0c;发现这个是Linux的一种机制&#xff0c;即当你输入密码时不显示&…

为什么阿里开发手册不建议使用Date类?

在日常编码中&#xff0c;基本上99%的项目都会有一个DateUtil工具类&#xff0c;而时间工具类里用的最多的就是java.util.Date。 大家都这么写&#xff0c;这还能有问题&#xff1f;&#xff1f; 当你的“默认常识”出现问题&#xff0c;这个打击&#xff0c;就是毁灭性的。 …

Python学习计划——7.2数据可视化

数据可视化是数据分析的重要组成部分&#xff0c;通过图表和图形将数据直观地展示出来&#xff0c;帮助我们发现数据中的模式和趋势。Python中常用的数据可视化库有matplotlib和seaborn。以下是对这些库的详细讲解及可运行的Python案例。 1. matplotlib 库 matplotlib 是一个…

Git 基础操作手册:轻松掌握常用命令

Git 操作完全手册&#xff1a;轻松掌握常用命令 引言一、暂存&#xff1a;git add ✏️二、提交&#xff1a;git commit &#x1f4dd;三、拉取、拉取合并 &#x1f504;四、推送&#xff1a;git push &#x1f310;五、查看状态&#xff1a;git status &#x1f4ca;六、查看历…

数据库管理-第225期 Oracle DB 23.5新特性一览(20240730)

数据库管理225期 2024-07-30 数据库管理-第225期 Oracle DB 23.5新特性一览&#xff08;20240730&#xff09;1 二进制向量维度格式2 RAC上的复制HNSW向量索引3 JSON集合4 JSON_ID SQL函数5 优化的通过网络对NVMe设备的Oracle的原生访问6 DBCA支持PMEM存储7 DBCA支持标准版高可…

[PM]面试题-工作问题

画一个原型需要多久?写一篇PRD文档需求多久? 时间长短取决于项目规模和业务难度, 规模大难度高,就要花费很长的时间, 规模下难度低时间就短, 一般来说, 1-2周的时间就可以完成原型和RED文档 市场需求文档写什么? 从打到下进行编写, 大的方面以市场为主体,包括市场规模, 发…

AI-PaddleOCR2.8在VS2019编译运行基于C++引擎推理CPU版本

1、下载PaddleOCR-release-2.8开源项目 https://github.com/PaddlePaddle/PaddleOCR https://github.com/PaddlePaddle/PaddleOCR/releases https://gitee.com/paddlepaddle/PaddleOCR?_fromgitee_search 2、下载安装Windows预测库 https://paddleinference.paddlepaddle.o…

轻量级服务器资源监控平台Beszel

什么是 Beszel &#xff1f; Beszel 是一个轻量级平台&#xff0c;借助 Beszel&#xff0c;可以访问 CPU 和内存使用情况的历史数据&#xff0c;以及 Docker 容器指标&#xff08;例如特定于容器的 CPU 和内存统计信息&#xff09;。还能收到针对潜在问题的可自定义警报通知&am…

【Docker】安装 Docker(Server-Centos、GUI-Windows11)—— 超详细教程

一、各版本平台支持情况 1、Server 版本 2、桌面版本 二、Server 版本安装&#xff08;Centos&#xff09; 1、安装依赖 &#xff08;1&#xff09;支持的操作系统 CentOS 7&#xff1a;推荐 CentOS 8 (stream) CentOS 9 (stream) &#xff08;2&#xff09;支持的 CPU A…

spring源码 循环依赖

spring框架两大核心&#xff1a;IOC和AOP IOC(Inverse of Control)控制反转 将对象的创建权交给 Spring 容器去创建&#xff0c;利用了工厂模式将对象交给容器管理&#xff0c;只需要在spring配置文件中配置相应的bean&#xff0c;以及设置相关的属性&#xff0c;让spring容器…

华为机试HJ76尼科彻斯定理

华为机试HJ76尼科彻斯定理 题目&#xff1a; 想法&#xff1a; 从题目可以找到规律&#xff0c;输出的第一个奇数为 ( 当前输入数值 − 1 ) 当前输入数值 1 (当前输入数值-1)当前输入数值1 (当前输入数值−1)当前输入数值1&#xff0c;输出是连续的输入数值个数个奇数&#…

具身智能又进一步!卡内基梅隆Meta苏黎世联邦实现虚拟人超灵活抓取

论文链接&#xff1a;https://arxiv.org/pdf/2407.11385 github链接&#xff1a;https://www.zhengyiluo.com/Omnigrasp-Site/ 亮点直击 本文设计了一种灵巧且通用的人形机器人运动表示&#xff0c;这显著提高了样本效率&#xff0c;并使得通过简单而有效的状态和奖励设计来学习…

51单片机嵌入式开发:22、STC89C52R控制 实现单总线温度传感器DS18b20的温度读取

STC89C52R控制 实现单总线温度传感器DS18b20的温度读取 1 概述1.1 介绍1.2 特点1.3 应用领域 2 DS18B20原理详解2.1 内部机理2.2 读写时序2.3 DS18B20操作代码程序 3 演示4 总结 配套演示例程 1 概述 DS18B20是一款数字温度传感器&#xff0c;由Maxim Integrated&#xff08;美…

【linux】【操作系统】head.s 源码阅读

head.s是Intel x86架构下的汇编语言代码&#xff0c;用于设置操作系统的内存管理和中断处理。主要完成以下内容&#xff1a; 设置数据段、代码段、附加段和全局段寄存器为0x10。设置堆栈指针为_stack_start。设置中断描述符表&#xff08;IDT&#xff09;和全局描述符表&#…

负载均衡、软件平滑升级

安装nginx 1.26.1 平滑升级、负载均衡 安装依赖 gcc gcc-c pcre-devel openssl-devel 七层负载均衡配置&#xff1a; [rootf ~]# vim /usr/local/nginx/conf/nginx.conf 43 location / {44 # root html;45 # index index.html index…

airtest的demo实现多设备并行

airtest的demo实现多设备并行 它实现是的获取adb连接上的所有设备&#xff0c;然后在每一台设备上跑给定的测试用例&#xff0c;跑完之后生成单机的测试报告&#xff0c;最后再汇总这些单机测试报告的结果&#xff0c;形成汇总&#xff08;聚合&#xff09;报告&#xff1a; 同…

html+css 实现4角移动悬停按钮

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;今天给大家分享htmlcss 绚丽效果&#xff01;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;创作不易&#xff0c;如果能帮助到大家或者给大家一些灵感和启发&#xff0c;欢迎收藏关注哦 &#x1f495; 文…