当前位置: 首页 > 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;
}
http://www.lryc.cn/news/63730.html

相关文章:

  • 鸿蒙Hi3861学习二-程序烧录与日志输出
  • typescript Awaited<Type>教程用法
  • AES硬件运算单元
  • mulesoft MCIA 破釜沉舟备考 2023.04.28.26 (易错题)
  • k210单片机定时器的应用
  • linux0.12-7-1
  • 设置 文本框 自动填充背景颜色 为白色
  • Bitmap引起的OOM问题
  • 【JavaEE初阶】认识线程(Thread)
  • 自动化运维工具一Ansible Roles实战
  • json 中有递归parentId节点转 c#实体类时如何处理
  • 给大家介绍几个手机冷门但好用的小技巧
  • 2.3 定点乘法运算
  • C++每日一练:打家劫室(详解动态规划法)
  • Wireshark使用
  • 这才是 SpringBoot 统一登录鉴权、异常处理、数据格式 的正确姿势
  • Java面试题总结 | Java面试题总结6-MYSQL模块(持续更新)
  • Linux命令集(Linux文件管理命令--mv指令篇)
  • 不一样的 Git 之间 | GitLab vs GitHub vs Gitee vs GitCode
  • 海尔牵头IEEE P2786国际标准通过Sponsor投票并连任工作组主席
  • 倾斜摄影超大场景的三维模型的顶层合并的纹理压缩与抽稀处理技术分析
  • linux命令之iostat详解
  • 【C++】程序员必备知识:认识类与对象
  • python基础实战5-python基本结构
  • 移动端异构运算技术 - GPU OpenCL 编程(基础篇)
  • QString类方法和变量简介(全)
  • 中移链控制台对接4A平台功能验证介绍
  • 必知的Facebook广告兴趣定位技巧,更准确地找到目标受众
  • 【MySQL】慢查询+SQL语句优化 (内容源自ChatGPT)
  • HashMap底层源码解析及红黑树分析