算法1-4 凌乱的yyy / 线段覆盖
题目描述
现在各大 oj 上有 n 个比赛,每个比赛的开始、结束的时间点是知道的。
yyy 认为,参加越多的比赛,noip 就能考的越好(假的)。
所以,他想知道他最多能参加几个比赛。
由于 yyy 是蒟蒻,如果要参加一个比赛必须善始善终,而且不能同时参加 2 个及以上的比赛。
输入格式
第一行是一个整数 n,接下来 n 行每行是 2 个整数 ai,bi (ai<bi),表示比赛开始、结束的时间。
输出格式
一个整数最多参加的比赛数目。
输入输出样例
输入 #1
3 0 2 2 4 1 3
输出 #1
2
说明/提示
- 对于 20% 的数据,n≤10;
- 对于 50% 的数据,n≤103;
- 对于 70% 的数据,n≤105;
- 对于 100% 的数据,1≤n≤106,0≤ai<bi≤106。
在一个数轴上有n条线段,现要选取其中k条线段使得这k条线段两两没有重合部分,问最大的k为多少。
最左边的线段放什么最好?
显然放右端点最靠左的线段最好,从左向右放,右端点越小妨碍越少
其他线段放置按右端点排序,贪心放置线段,即能放就放。
#include<iostream>
#include<algorithm>
using namespace std;int n;
int ans=1;
int last_end_time; //上一场比赛结束的时间 C++ 标准库中有个 time 函数,这里不能取timestruct match{int begin; //比赛开始时间 int end; //比赛结束时间
}m[1000010];bool cmp(match x, match y)
{return x.end < y.end;
}int main()
{cin>>n;for(int i=0; i<=n-1; ++i){cin>>m[i].begin;cin>>m[i].end;}//按照比赛结束的早晚排序 结束的早的放在前 sort(m, m+n, cmp);//结束最早的那场比赛一定可以参加 last_end_time = m[0].end;//从第二个比赛开始找for(int i=1; i<=n-1; ++i){//当前比赛的开始时间大于等于上场比赛的结束时间if(m[i].begin >= last_end_time){ans++;last_end_time = m[i].end;}}cout<<ans;return 0;
}
相关文章:
算法1-4 凌乱的yyy / 线段覆盖
题目描述 现在各大 oj 上有 n 个比赛,每个比赛的开始、结束的时间点是知道的。 yyy 认为,参加越多的比赛,noip 就能考的越好(假的)。 所以,他想知道他最多能参加几个比赛。 由于 yyy 是蒟蒻,…...
【计网】数据链路层
数据链路层 3.1 数据链路层概述3.2 封装成帧3.3 差错检测3.4 可靠传输3.4.1 可靠传输的概念3.4.2 可靠传输的实现机制 - 停止等待协议3.4.3 可靠传输的实现机制 -回退N帧协议3.4.4 可靠传输的实现机制 -选择重传协议 3.5 点对点协议3.5.1 帧格式3.5.2 透明传输 3.6 媒体接入控制…...
javaweb自用笔记:Vue
Vue 什么是vue vue案例 1、引入vue.js文件 2、定义vue对象 3、定义vue接管的区域el 4、定义数据模型data 5、定义视图div 6、通过标签v-model来绑定数据模型 7、{{message}}直接将数据模型message展示出来 8、由于vue的双向数据绑定,当视图层标签input里的…...
CSS Overflow 属性详解
CSS Overflow 属性详解 在网页设计和开发中,CSS Overflow 属性是一个非常重要的特性,它决定了当内容超出其容器大小时应该如何处理。本文将详细介绍 CSS Overflow 属性的相关知识,包括其语法、作用、常用属性值以及一些实际应用场景。 1. CSS Overflow 属性概述 CSS Over…...
沃丰科技结合DeepSeek大模型技术落地与应用前后效果对比
技术突破:DeepSeek算法创新,显著降低了显存占用和推理成本。仅需少量标注数据即可提升推理能力。这种突破减少了对海量数据的依赖,削弱了数据垄断企业的优势! 商业模式颠覆:DeepSeek选择完全开源模式,迫使…...
突破光学成像局限:全视野光学血管造影技术新进展
全视野光学血管造影(FFOA)作为一种实时、无创的成像技术,能够提取生物血液微循环信息,为深入探究生物组织的功能和病理变化提供关键数据。然而,传统FFOA成像方法受到光学镜头景深(DOF)的限制&am…...
2.反向传播机制简述——大模型开发深度学习理论基础
在深度学习开发中,反向传播机制是训练神经网络不可或缺的一部分。它让模型能够通过不断调整权重,从而将预测误差最小化。本文将从实际开发角度出发,简要介绍反向传播机制的核心概念、基本流程、在现代网络中的扩展,以及如何利用自…...
机器学习校招面经二
快手 机器学习算法 一、AUC(Area Under the ROC Curve)怎么计算?AUC接近1可能的原因是什么? 见【搜广推校招面经四】 AUC 是评估分类模型性能的重要指标,用于衡量模型在不同阈值下区分正负样本的能力。它是 ROC 曲线…...
Spring Boot如何利用Twilio Verify 发送验证码短信?
Twilio提供了一个名为 Twilio Verify 的服务,专门用于处理验证码的发送和验证。这是一个更为简化和安全的解决方案,适合需要用户身份验证的应用。 使用Twilio Verify服务的步骤 以下是如何在Spring Boot中集成Twilio Verify服务的步骤: 1.…...
毕业项目推荐:基于yolov8/yolo11的苹果叶片病害检测识别系统(python+卷积神经网络)
文章目录 概要一、整体资源介绍技术要点功能展示:功能1 支持单张图片识别功能2 支持遍历文件夹识别功能3 支持识别视频文件功能4 支持摄像头识别功能5 支持结果文件导出(xls格式)功能6 支持切换检测到的目标查看 二、数据集三、算法介绍1. YO…...
Linux的用户与权限--第二天
认知root用户(超级管理员) root用户用于最大的系统操作权限 普通用户的权限,一般在HOME目录内部不受限制 su与exit命令 su命令: su [-] 用户名 -符号是可选的,表示切换用户后加载环境变量 参数为用户名,…...
【Flink银行反欺诈系统设计方案】1.短时间内多次大额交易场景的flink与cep的实现
【flink应用系列】1.Flink银行反欺诈系统设计方案 1. 经典案例:短时间内多次大额交易1.1 场景描述1.2 风险判定逻辑 2. 使用Flink实现2.1 实现思路2.2 代码实现2.3 使用Flink流处理 3. 使用Flink CEP实现3.1 实现思路3.2 代码实现 4. 总结 1. 经典案例:短…...
HashMap的table数组何时初始化?默认容量和扩容阈值是多少?
HashMap 的 table 数组何时初始化? 答案: table 数组在第一次调用 put() 方法时初始化。 为什么? HashMap 为了节省内存,采用了“懒加载”机制。即使用 new HashMap() 创建对象时,只是计算了参数(如容量、…...
基于CURL命令封装的JAVA通用HTTP工具
文章目录 一、简要概述二、封装过程1. 引入依赖2. 定义脚本执行类 三、单元测试四、其他资源 一、简要概述 在Linux中curl是一个利用URL规则在命令行下工作的文件传输工具,可以说是一款很强大的http命令行工具。它支持文件的上传和下载,是综合传输工具&…...
docker学习笔记(1)从安装docker到使用Portainer部署容器
docker学习笔记第一课 先交代背景 docker宿主机系统:阿里云ubuntu22.04 开发机系统:win11 docker镜像仓库:阿里云,此阿里云与宿主机系统没有关系,是阿里云提供的一个免费的docker仓库 代码托管平台:github&…...
数据集/API 笔记:新加坡PSI(空气污染指数)API
data.gov.sg 数据范围:2016年2月 - 2025年3月 1 获取API方式 curl --request GET \--url https://api-open.data.gov.sg/v2/real-time/api/psi 2 返回数据 API 的数据结构可以分为 3 大部分: 区域元数据(regionMetadata) →…...
计算机网络数据传输探秘:包裹如何在数字世界旅行?
计算机网络数据传输探秘:包裹如何在数字世界旅行? 一、从快递网络看数据传输本质 想象你网购了一件商品: 打包:商家用纸箱包装,贴上地址标签(数据封装)运输:包裹经过网点→分拣中心→运输车(网络节点与链路)签收:快递员核对信息后交付(数据校验与接收)数据的网络…...
笔记:代码随想录算法训练营day36:LeetCode1049. 最后一块石头的重量 II、494. 目标和、474.一和零
学习资料:代码随想录 1049.最后一块石头的重量II 力扣题目链接 思路:如何讲该问题转化为背包问题:还是对半分去碰,对半分去碰碰剩下的就是最小的。然后背包容量就是一半儿,物品重量等于物品价值等于stones[i] 和上…...
Bitmap -> Bitmap安卓设备上的显示和内存
Android 屏幕显示与 Bitmap 内存详解 前言 在 Android 开发中,理解屏幕显示单位和 Bitmap 内存占用是构建高效应用的基础。本文将详细介绍相关概念、计算公式及单位转换,并通过实例分析 Bitmap 在内存中的表现。 一、屏幕显示单位基础 1.1 基本单位及…...
QT study DAY2
作业 代码 Widget.h class Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);~Widget();void save_data(const QString& filename,const QString& data); private slots:void on_lineEdit_textChanged(); //账户栏void on_l…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
C++.OpenGL (20/64)混合(Blending)
混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时,性能会显著下降。以下是优化思路和简易实现方法: 一、核心优化思路 减少 JOIN 数量 数据冗余:添加必要的冗余字段(如订单表直接存储用户名)合并表:将频繁关联的小表合并成…...
学习一下用鸿蒙DevEco Studio HarmonyOS5实现百度地图
在鸿蒙(HarmonyOS5)中集成百度地图,可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API,可以构建跨设备的定位、导航和地图展示功能。 1. 鸿蒙环境准备 开发工具:下载安装 De…...
Modbus RTU与Modbus TCP详解指南
目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...
