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

最多能打多少场比赛呢

凌乱的yyy / 线段覆盖

题目背景

快 noip 了,yyy 很紧张!

题目描述

现在各大 oj 上有 n n n 个比赛,每个比赛的开始、结束的时间点是知道的。

yyy 认为,参加越多的比赛,noip 就能考的越好(假的)。

所以,他想知道他最多能参加几个比赛。

由于 yyy 是蒟蒻,如果要参加一个比赛必须善始善终,而且不能同时参加 2 2 2 个及以上的比赛。

输入格式

第一行是一个整数 n n n ,接下来 n n n 行每行是 2 2 2 个整数 a i , b i a_{i},b_{i} ai,bi ( a i < b i a_{i}<b_{i} ai<bi ),表示比赛开始、结束的时间。

输出格式

一个整数最多参加的比赛数目。

样例 #1

样例输入 #1

3
0 2
2 4
1 3

样例输出 #1

2

提示

对于 20 % 20\% 20% 的数据, n ≤ 10 n \le 10 n10

对于 50 % 50\% 50% 的数据, n ≤ 1 0 3 n \le 10^3 n103

对于 70 % 70\% 70% 的数据, n ≤ 1 0 5 n \le 10^{5} n105

对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 1 0 6 1\le n \le 10^{6} 1n106 0 ≤ a i < b i ≤ 1 0 6 0 \le a_{i} < b_{i} \le 10^6 0ai<bi106

思路

要求最多能打多少场比赛,那么早结束的比赛就要先打,所以要按比赛结束时间来排序。设定一个变量en来储存上一次比赛结束时间,如果这一次比赛开始时间大于等于上一次比赛结束时间,那么这场比赛就可以打,接着更新en为这次比赛结束时间,方便下一个比较。这里我想分享一下我讨论的一个问题:当区间包含的时候,比如2 3、2 4、3 4,因为原先按比赛结束时间排好了序,所以2 3会打,然后因为2 4的比赛开始时间小于2 3比赛结束时间,所以2 4不会打,接着 3 4会打。也就是说,区间重合时,会筛选出区间内的比赛。因为最外层的那场比赛开始时间小,结束时间大,会被筛掉的。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
struct Tim
{int s,e;
}t[N];
bool cmp(Tim a,Tim b)
{return a.e<b.e;//按照比赛结束时间从小到大排序
}
int main()
{int n;cin>>n;for(int i=0;i<n;i++){cin>>t[i].s>>t[i].e;}sort(t,t+n,cmp);int en=0;long long cnt=0;for(int i=0;i<n;i++){if(t[i].s>=en)//大于上次比赛结束时间,区间不重合{en=t[i].e;//更新比赛结束时间cnt++;}else{continue;}}cout<<cnt;return 0;
}

相关文章:

最多能打多少场比赛呢

凌乱的yyy / 线段覆盖 题目背景 快 noip 了&#xff0c;yyy 很紧张&#xff01; 题目描述 现在各大 oj 上有 n n n 个比赛&#xff0c;每个比赛的开始、结束的时间点是知道的。 yyy 认为&#xff0c;参加越多的比赛&#xff0c;noip 就能考的越好&#xff08;假的&#x…...

鸿蒙Hi3861学习二-程序烧录与日志输出

一、准备事项 开发板&#xff1a;BearPi-Hm Nano windows工具&#xff1a;HiBurn.exe https://pan.baidu.com/s/18OQD1_BvjNKD_J2e2iX3qg?pwdadrs 提取码&#xff1a;adrs windows工具&#xff1a;MobaXterm和RaiDrive 把ubuntu文件夹映射到windows本地。可以参考如下链接&am…...

typescript Awaited<Type>教程用法

typescript Awaited教程用法 文章目录 typescript Awaited<Type>教程用法 ts4.5发布了Awaited&#xff0c;但是很多人不明白Awaited的用法。 首先看一下官方的说明&#xff1a;这种类型旨在模拟函数await中的操作async&#xff0c;或 s.then()上的方法——特别是它们递归…...

AES硬件运算单元

功能描述 AES单元主要功能如下: 支持解密密钥扩展 支持128bit/192bit/256bit的密钥长度支持ECBCBCCTRM支持DMA进行自动数据传输 支持GF(2^128)域下的乘法&#xff0c;支持GMAC 工作模式 AES有4种工作模式&#xff0c;通过配置MODE1:0]寄存器设置。 模式1:用存储在AES KEYRx寄存…...

mulesoft MCIA 破釜沉舟备考 2023.04.28.26 (易错题)

mulesoft MCIA 破釜沉舟备考 2023.04.28.26 (易错题) 1. According to MuleSoft, what is a major distinguishing characteristic of an application network in relation to the integration of systems, data, and devices?2. An integration team follows MuleSoft’s r…...

k210单片机定时器的应用

定时器应该是一个单片机的标准配置&#xff0c;所以k210也是有的&#xff0c;拥有3个定时器&#xff0c;具体的使用方法我们往下看&#xff1a; 分步介绍&#xff1a; 首先是相关模块的使用 构造函数&#xff1a; machine.Timer(id,channel,modeTimer.MODE_ONE_SHOT,period100…...

linux0.12-7-1

[272页] 第7章 初始化程序 1、main.c主要内核初始化工作。 2、如果能完全理解这里调用的所有程序&#xff0c;那么看完这张内容后应该对Linux内核有了大致的了解。 3、 有一定的C语言知识 4、 需要GNU gcc手册在身边作为参考&#xff0c;因为在内核代码很多地方使用gcc的扩展…...

设置 文本框 自动填充背景颜色 为白色

关于autofill伪类的 兼容性&#xff1a; 在现代浏览器中&#xff0c;包括Chrome、Safari、Firefox等&#xff0c;都支持:autofill伪类&#xff0c;但在使用时必须加上浏览器前缀-webkit-&#xff0c;即:-webkit-autofill。 在旧版的浏览器中&#xff0c;可能不支持:autofill伪…...

Bitmap引起的OOM问题

作者&#xff1a;向阳逐梦 1.什么是OOM&#xff1f;为什么会引起OOM&#xff1f; 答&#xff1a;Out Of Memory(内存溢出)&#xff0c;我们都知道Android系统会为每个APP分配一个独立的工作空间&#xff0c;或者说分配一个单独的Dalvik虚拟机&#xff0c;这样每个APP都可以独立…...

【JavaEE初阶】认识线程(Thread)

目录 &#x1f33e; 前言 &#x1f33e; 了解线程 &#x1f308;1.1 线程是什么&#xff1f; &#x1f308;1.2 一些基本问题 &#x1f33e;2、创建线程的方式 &#x1f308; 2.1 继承Thread类 &#x1f308; 2.2 实现Runnable接口并重写run()方法 &#x1f308; 注意…...

自动化运维工具一Ansible Roles实战

目录 一、Ansible Roles概述 1.1.roles官方的目录结构 1.2.Ansible Roles依赖关系 二、Ansible Roles案例实战 2.1.Ansible Roles NFS服务 2.2 Roles Memcached 2.3 Roles-rsync服务 一、Ansible Roles概述 之前介绍了 Playbook 的使用方法&#xff0c;对于批量任务的部…...

json 中有递归parentId节点转 c#实体类时如何处理

如果您有一个具有递归parentId节点的JSON数据&#xff0c;并且您需要将其转换为C#实体类&#xff0c;则可以使用以下方法&#xff1a; 创建一个类来表示JSON对象的节点&#xff0c;包括它的属性和子节点。 public class Node {public int Id { get; set; }public string Name …...

给大家介绍几个手机冷门但好用的小技巧

技巧一&#xff1a;拍照识别植物 手机的拍照识别植物功能是指在使用手机相机时&#xff0c;可以通过对植物进行拍照&#xff0c;并通过植物识别技术&#xff0c;获取植物的相关信息和资料。其主要优点如下&#xff1a; 方便实用&#xff1a;使用拍照识别植物功能&#xff0c;…...

2.3 定点乘法运算

学习目标&#xff1a; 如果我要学习定点乘法运算&#xff0c;我会按照以下步骤进行学习&#xff1a; 确定学习目标&#xff1a;明确学习定点乘法运算的目的和重点&#xff0c;以便有针对性地进行学习。 掌握基础知识&#xff1a;首先需要了解定点数和定点乘法的基础知识&…...

C++每日一练:打家劫室(详解动态规划法)

文章目录 前言一、题目二、分析三、代码总结 前言 这题目出得很有意思哈&#xff0c;打劫也是很有技术含量滴&#xff01;不会点算法打劫这么粗暴的工作都干不好。 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、题目 题目名称&#xff1a; 打家…...

Wireshark使用

Capture Filters 语法 <Protocol name><Direction><Hosts><Value><Logical operations><Expressions> e.g 1.tcp src port 443 只抓取来源端口是443的tcp数据 2.not arp 不获取arp数据 3.port 80 获取端口是80的数据&#xff0c;不指…...

这才是 SpringBoot 统一登录鉴权、异常处理、数据格式 的正确姿势

本篇将要学习 Spring Boot 统一功能处理模块&#xff0c;这也是 AOP 的实战环节 用户登录权限的校验实现接口 HandlerInterceptor WebMvcConfigurer 异常处理使用注解 RestControllerAdvice ExceptionHandler 数据格式返回使用注解 ControllerAdvice 并且实现接口 Response…...

Java面试题总结 | Java面试题总结6-MYSQL模块(持续更新)

Mysql 文章目录 Mysql关系型数据库和非关系型数据库的区别什么是ORM?-**mybatis**如何评估一个索引创建的是否合理&#xff1f;Count函数执行效果上&#xff1a;执行效率上&#xff1a;count(主键)和count(列名) 数据库的三大范式Mysql中char和varchar的区别数据库设计或者功能…...

Linux命令集(Linux文件管理命令--mv指令篇)

Linux命令集&#xff08;Linux文件管理命令--mv指令篇&#xff09; Linux文件管理命令集&#xff08;mv指令篇&#xff09;2. mv(move)1. 文件移动2. 递归移动目录3. 文件目录重命名4. 强制移动5. 备份覆盖的目标文件6. 试探性移动7. 显示移动进度8. 补集操作9. 修改文件的权限…...

不一样的 Git 之间 | GitLab vs GitHub vs Gitee vs GitCode

Git仓库对比&#xff1a;GitLab vs GitHub vs Gitee vs GitCode 在软件开发中&#xff0c;版本控制是必不可少的工具之一。Git作为目前最为流行的版本控制系统&#xff0c;也逐渐成为了开发者们的标配。但是&#xff0c;如何选择一个合适的Git仓库来存储您的代码呢&#xff1f;…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...