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

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...