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

算法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 个比赛&#xff0c;每个比赛的开始、结束的时间点是知道的。 yyy 认为&#xff0c;参加越多的比赛&#xff0c;noip 就能考的越好&#xff08;假的&#xff09;。 所以&#xff0c;他想知道他最多能参加几个比赛。 由于 yyy 是蒟蒻&#xff0c…...

【计网】数据链路层

数据链路层 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的双向数据绑定&#xff0c;当视图层标签input里的…...

CSS Overflow 属性详解

CSS Overflow 属性详解 在网页设计和开发中,CSS Overflow 属性是一个非常重要的特性,它决定了当内容超出其容器大小时应该如何处理。本文将详细介绍 CSS Overflow 属性的相关知识,包括其语法、作用、常用属性值以及一些实际应用场景。 1. CSS Overflow 属性概述 CSS Over…...

沃丰科技结合DeepSeek大模型技术落地与应用前后效果对比

技术突破&#xff1a;DeepSeek算法创新&#xff0c;显著降低了显存占用和推理成本。仅需少量标注数据即可提升推理能力。这种突破减少了对海量数据的依赖&#xff0c;削弱了数据垄断企业的优势&#xff01; 商业模式颠覆&#xff1a;DeepSeek选择完全开源模式&#xff0c;迫使…...

突破光学成像局限:全视野光学血管造影技术新进展

全视野光学血管造影&#xff08;FFOA&#xff09;作为一种实时、无创的成像技术&#xff0c;能够提取生物血液微循环信息&#xff0c;为深入探究生物组织的功能和病理变化提供关键数据。然而&#xff0c;传统FFOA成像方法受到光学镜头景深&#xff08;DOF&#xff09;的限制&am…...

2.反向传播机制简述——大模型开发深度学习理论基础

在深度学习开发中&#xff0c;反向传播机制是训练神经网络不可或缺的一部分。它让模型能够通过不断调整权重&#xff0c;从而将预测误差最小化。本文将从实际开发角度出发&#xff0c;简要介绍反向传播机制的核心概念、基本流程、在现代网络中的扩展&#xff0c;以及如何利用自…...

机器学习校招面经二

快手 机器学习算法 一、AUC&#xff08;Area Under the ROC Curve&#xff09;怎么计算&#xff1f;AUC接近1可能的原因是什么&#xff1f; 见【搜广推校招面经四】 AUC 是评估分类模型性能的重要指标&#xff0c;用于衡量模型在不同阈值下区分正负样本的能力。它是 ROC 曲线…...

Spring Boot如何利用Twilio Verify 发送验证码短信?

Twilio提供了一个名为 Twilio Verify 的服务&#xff0c;专门用于处理验证码的发送和验证。这是一个更为简化和安全的解决方案&#xff0c;适合需要用户身份验证的应用。 使用Twilio Verify服务的步骤 以下是如何在Spring Boot中集成Twilio Verify服务的步骤&#xff1a; 1.…...

毕业项目推荐:基于yolov8/yolo11的苹果叶片病害检测识别系统(python+卷积神经网络)

文章目录 概要一、整体资源介绍技术要点功能展示&#xff1a;功能1 支持单张图片识别功能2 支持遍历文件夹识别功能3 支持识别视频文件功能4 支持摄像头识别功能5 支持结果文件导出&#xff08;xls格式&#xff09;功能6 支持切换检测到的目标查看 二、数据集三、算法介绍1. YO…...

Linux的用户与权限--第二天

认知root用户&#xff08;超级管理员&#xff09; root用户用于最大的系统操作权限 普通用户的权限&#xff0c;一般在HOME目录内部不受限制 su与exit命令 su命令&#xff1a; su [-] 用户名 -符号是可选的&#xff0c;表示切换用户后加载环境变量 参数为用户名&#xff0c…...

【Flink银行反欺诈系统设计方案】1.短时间内多次大额交易场景的flink与cep的实现

【flink应用系列】1.Flink银行反欺诈系统设计方案 1. 经典案例&#xff1a;短时间内多次大额交易1.1 场景描述1.2 风险判定逻辑 2. 使用Flink实现2.1 实现思路2.2 代码实现2.3 使用Flink流处理 3. 使用Flink CEP实现3.1 实现思路3.2 代码实现 4. 总结 1. 经典案例&#xff1a;短…...

HashMap的table数组何时初始化?默认容量和扩容阈值是多少?

HashMap 的 table 数组何时初始化&#xff1f; 答案&#xff1a; table 数组在第一次调用 put() 方法时初始化。 为什么&#xff1f; HashMap 为了节省内存&#xff0c;采用了“懒加载”机制。即使用 new HashMap() 创建对象时&#xff0c;只是计算了参数&#xff08;如容量、…...

基于CURL命令封装的JAVA通用HTTP工具

文章目录 一、简要概述二、封装过程1. 引入依赖2. 定义脚本执行类 三、单元测试四、其他资源 一、简要概述 在Linux中curl是一个利用URL规则在命令行下工作的文件传输工具&#xff0c;可以说是一款很强大的http命令行工具。它支持文件的上传和下载&#xff0c;是综合传输工具&…...

docker学习笔记(1)从安装docker到使用Portainer部署容器

docker学习笔记第一课 先交代背景 docker宿主机系统&#xff1a;阿里云ubuntu22.04 开发机系统&#xff1a;win11 docker镜像仓库&#xff1a;阿里云&#xff0c;此阿里云与宿主机系统没有关系&#xff0c;是阿里云提供的一个免费的docker仓库 代码托管平台&#xff1a;github&…...

数据集/API 笔记:新加坡PSI(空气污染指数)API

data.gov.sg 数据范围&#xff1a;2016年2月 - 2025年3月 1 获取API方式 curl --request GET \--url https://api-open.data.gov.sg/v2/real-time/api/psi 2 返回数据 API 的数据结构可以分为 3 大部分&#xff1a; 区域元数据&#xff08;regionMetadata&#xff09; →…...

计算机网络数据传输探秘:包裹如何在数字世界旅行?

计算机网络数据传输探秘:包裹如何在数字世界旅行? 一、从快递网络看数据传输本质 想象你网购了一件商品: 打包:商家用纸箱包装,贴上地址标签(数据封装)运输:包裹经过网点→分拣中心→运输车(网络节点与链路)签收:快递员核对信息后交付(数据校验与接收)数据的网络…...

笔记:代码随想录算法训练营day36:LeetCode1049. 最后一块石头的重量 II、494. 目标和、474.一和零

学习资料&#xff1a;代码随想录 1049.最后一块石头的重量II 力扣题目链接 思路&#xff1a;如何讲该问题转化为背包问题&#xff1a;还是对半分去碰&#xff0c;对半分去碰碰剩下的就是最小的。然后背包容量就是一半儿&#xff0c;物品重量等于物品价值等于stones[i] 和上…...

Bitmap -> Bitmap安卓设备上的显示和内存

Android 屏幕显示与 Bitmap 内存详解 前言 在 Android 开发中&#xff0c;理解屏幕显示单位和 Bitmap 内存占用是构建高效应用的基础。本文将详细介绍相关概念、计算公式及单位转换&#xff0c;并通过实例分析 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…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

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

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