当前位置: 首页 > 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;…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...