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

AcWing907. 区间覆盖

参考的视频讲解:↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
【贪心算法08-区间问题03-区间覆盖】
每次贪心就是选择左端点里面<起始端点里面右边界最大的,这样就是保证了最少区间个数!
然后每次迭代都会更新一次起始端点st,反复运用本算法。
一定要仔细看视频讲解!!!

#include<iostream>
#include<algorithm>
#define N 100010
#define INF 2e9
using namespace std;
int n ;
struct Range{int l, r;bool operator<(const Range& r1){return l < r1.l;}
}range[N];
int main(){int st , ed;cin >> st >> ed;cin >> n;for(int i = 0 ; i < n ; ++ i){int l , r ;cin >> l >> r;range[i] = {l ,r};} sort(range,range + n);int res = 0 ;bool success = false;for(int i = 0 ; i < n ; ++ i){int j = i ,r = -2e9;while(j < n && range[j].l <= st){r = max(r , range[j].r);++ j;}if(r < st){res = -1;//如果挑出来的最大右端点小于起始端点,那么无解,返回-1break;}++res;if(r >= ed){//如果右边界已经可以超过末尾端点ed,那么求解完毕,返回ressuccess = true;break;}st = r;i = j - 1;}if (!success) res = -1;printf("%d\n", res);
}

相关文章:

AcWing907. 区间覆盖

参考的视频讲解&#xff1a;↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 【贪心算法08-区间问题03-区间覆盖】 每次贪心就是选择左端点里面&#xff1c;起始端点里面右边界最大的&#xff0c;这样就是保证了最少区间个数! 然后每次迭代都会更新一次起始端点st&#xff0c;反复运用本算法…...

Unity TMP (TextMeshPro) 更新中文字符集

TMP更新中文字符集 1 字符集缺失说明2 字体的字符表2.1 字符表更新模式&#xff1a;动态2.2 字符表更新模式&#xff1a;静态 3 更新字符集步骤3.1 打开纹理更新面板3.1 导入文本文件3.3 关于警告处理 4 修改TMP默认字体设置 1 字符集缺失说明 使用TMP显示中文需要用到中文字体…...

Leetcode3259. 超级饮料的最大强化能量

Every day a Leetcode 题目来源&#xff1a;3259. 超级饮料的最大强化能量 解法1&#xff1a;记忆化搜索 本题的状态定义 dfs(i,j)。其中 j0,1&#xff0c;分别表示最后选的是 energyDrinkA[i] 还是 energyDrinkB[i]。 为方便实现&#xff0c;把 energyDrinkA 和 energyDri…...

Java题集(由入门到精通)03

此系列文章收录大量Java经典代码题&#xff08;也可以算是leetcode刷题指南&#xff09;&#xff0c;希望可以与大家一起努力学好Java。3、2、1&#xff0c;请看&#xff01; 目录 1.创建学生成绩表 2.冒泡排序 3.模拟彩票中奖 4.杨辉三角 1.创建学生成绩表 输入n个学生的…...

zblog自动生成文章插件(百度AI写作配图,图文并茂)

最近工作比较忙&#xff0c;导致自己的几个网站都无法手动更新&#xff0c;于是乎也想偷个懒把&#xff0c;让AI帮忙打理下自己的网站。我接触chatgpt等AI工具还是比较早了&#xff0c;从openai推出gpt3.5就一直在用&#xff0c;说实话&#xff0c;开始的时候用AI自动更新网站还…...

华为 HCIP-Datacom H12-821 题库 (4)

有需要题库的可以看主页置顶 V群仅进行学习交流 1.缺省情况下&#xff0c;广播型网络中运行 IS-IS 的路由器&#xff0c;DIS 发送 CSNP报文的周期为多少秒&#xff1f; A、10 B、3.3 C、30 D、40 答案&#xff1a;A 解析&#xff1a; 广播型网络中运行 IS-IS 的路由器&am…...

使用seq_file

在《使用procfs》一文的源码示例中有说到proc文件系统每次读取的数据只能是1个页,如果超过则需多次读取,这样的话会增加读取次数,增多系统调用次数,影响了整体的效率,故而才有seq file序列文件的出现,该项功能使得内核对于大文件的读取更加容易。 对于seq file,其结构…...

期货赫兹量化-种群优化算法:进化策略,(μ,λ)-ES 和 (μ+λ)-ES

进化策略&#xff08;Evolution Strategies, ES&#xff09;是一种启发式算法&#xff0c;旨在模仿自然选择的过程来解决复杂的优化问题&#xff0c;尤其在没有显式解、或搜索空间巨大的情况下表现良好。基于自然界的进化原理&#xff0c;进化策略通过突变、选择等遗传算子迭代…...

pytest实战演练

pytest实战演练 pycharm常见操作 创建项目使用虚拟环境 创建文件夹的时候建议使用的创建方式 这样创建是因为python3.0版本之后导包无区别&#xff0c;之前版本导包会报错的 _init_.py文件中建议为空不写内容 _all_[]的含义 是将列表中的方法或变量或类暴漏出去便于使用的生效…...

7、关于LoFTR

7、关于LoFTR LoFTR论文链接&#xff1a;LoFTR LoFTR的提出&#xff0c;是将Transformer模型的注意力机制在特征匹配方向的应用&#xff0c;Transformer的提取特征的机制&#xff0c;在自身进行&#xff0c;本文提出可以的两张图像之间进行特征计算&#xff0c;非常适合进行特…...

硬件工程师笔试面试知识器件篇——电感

目录​​​​​​​ 3、电感 3.1、基础 电感原理图 电感实物图 3.1.1、定义与单位 1)定义: 2) 单位: 3.1.2、物理原理 1)法拉第电磁感应定律: 2)楞次定律: 3.1.3、电感器的构造 3.1.4、类型 3.1.5、应用 3.1.6、特性 3.1.7、设计考虑 3.2、相关问题 3.…...

代码随想录八股训练营第三十六天| C++

前言 一、push_back()和emplace_back()的区别&#xff1f; 1.1.push_back(): 1.2.emplace_back(): 1.3.区别总结&#xff1a; 1.4.使用场景: 二、map dequeu list 的实现原理&#xff1f; 2.1.std::map: 2.2. std::deque: 2.3. std::list: 2.4. 区别总结: 总结 前言…...

学习计算机网络

a类0~127&#xff0c;b类128~191&#xff0c;c类192~223 网络地址&#xff1a;看子网掩码&#xff0c;分网络位和主机位&#xff0c;后面是主机位&#xff0c;主机位全部为0&#xff0c;网络地址。 直接广播地址&#xff1a;看子网掩码&#xff0c;分网络位和主机位&#xff…...

Django发送邮件

【图书介绍】《Django 5企业级Web应用开发实战&#xff08;视频教学版&#xff09;》_django 5企业级web应用开发实战(视频教学版)-CSDN博客 Django 5框架Web应用开发_夏天又到了的博客-CSDN博客 本文学习怎么使用Django发送邮件。 尽管使用Python的smtplib模块发送电子邮件…...

T7:咖啡豆识别

T7&#xff1a;咖啡豆识别 **一、前期工作**1.设置GPU,导入库2.导入数据3.查看数据 **二、数据预处理**1.加载数据2.可视化数据3.配置数据集 **三、构建CNN网络模型**1、手动搭建2、直接调用官方模型 **四、编译模型****五、训练模型****六、模型评估****七、预测**八、暂时总结…...

【MATLAB】FIR滤波器的MATLAB实现

FIR滤波器的MATLAB实现 FIR滤波器的设计fir1函数fir2函数 与IIR滤波器相比&#xff0c;FIR滤波器既有其优势也有其局限性。FIR滤波器的主要优点包括&#xff1a; 精确的线性相位响应&#xff1b;永远保持稳定性&#xff1b;设计方法通常是线性的&#xff1b;在硬件实现中具有更…...

【RabbitMQ之一:windows环境下安装RabbitMQ】

目录 一、下载并安装Erlang1、下载Erlang2、安装Erlang3、配置环境变量4、验证erlang是否安装成功 二、下载并安装RabbitMQ1、下载RabbitMQ2、安装RabbitMQ3、配置环境变量4、验证RabbitMQ是否安装成功5、启动RabbitMQ服务&#xff08;安装后服务默认自启动&#xff09; 三、安…...

ISO26262和Aspice之间的关联

ASPICE 介绍&#xff1a; ASPICE&#xff08;Automotive Software Process Improvement and Capability dEtermination&#xff09;是汽车软件过程改进及能力评定的模型&#xff0c;它侧重于汽车软件的开发过程。ASPICE 定义了一系列的过程和活动&#xff0c;包括需求管理、软…...

对极约束及其性质 —— 公式详细推导

Title: 对极约束及其性质 —— 公式详细推导 文章目录 前言1. 对极约束 (Epipolar Constraint)2. 坐标转换 (Coordinate Transformations)3. 像素坐标 (Pixel Coordinates)4. 像素坐标转换 (Transformations of Pixel Coordinates)5. 本质矩阵 (Essential Matrix)6. 线坐标 (Co…...

【论文精读】SCINet-基于降采样和交互学习的时序卷积模型

《SCINet: Time Series Modeling and Forecasting with Sample Convolution and Interaction》的作者团队来自香港中文大学,发表在NeurIPS 2022会议上。 动机 该论文的出发点是观察到时间序列数据具有独特的属性:即使在将时间序列下采样成两个子序列后,时间关系(例如数据…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...