【洛谷 P1803】凌乱的yyy _ 线段覆盖 题解(贪心算法+结构体排序)

简介: **线段覆盖问题**: YYY 想在 NOIP 前参加最多比赛。给定 $n$ 场比赛的开始和结束时间,每场比赛必须连续且不能冲突。输入包含每场比赛的时间段,输出最多可参加的比赛数。$20\%$ 数据 $n\leq10$,$50\%$ 数据 $n\leq10^3$,$100\%$ 数据 $n\leq10^6$。解决方案:按结束时间排序比赛,若当前比赛开始时间晚于上一个结束时间,则计数加一。样例输入:3 场比赛,输出:2。AC C++ 代码实现了此算法。

凌乱的yyy / 线段覆盖

题目背景

快 noip 了,yyy 很紧张!

题目描述

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

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

3
0 2
2 4
1 3

样例输出 #1

2

提示

对于 $20\%$ 的数据, $n \le 10$。

对于 $50\%$ 的数据, $n \le 10^3$。

对于 $70\%$ 的数据, $n \le 10^{5}$。

对于 $100\%$ 的数据, $1\le n \le 10^{6}$ , $0 \le a{i} < b{i} \le 10^6$。

思路

先按结束时间对结构体数组进行排序。若比赛的开始时间晚于上一个比赛的结束时间,则选取该比赛。

AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
#define AUTHOR "HEX9CF"
using namespace std;

const int maxn = 100005;

int n;
int cnt = 0;
int las = 0;

struct S
{
   
    int u;
    int v;
} a[maxn];

bool cmp(S x, S y)
{
   
    return x.v < y.v;
}

int main()
{
   
    cin >> n;
    for (int i = 0; i < n; i++)
    {
   
        cin >> a[i].u >> a[i].v;
    }
    sort(a, a + n, cmp);
    for (int j = 0; j < n; j++)
    {
   
        if (las <= a[j].u)
        {
   
            las = a[j].v;
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}
目录
相关文章
|
10天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
|
11天前
|
机器学习/深度学习 运维 算法
基于非支配排序遗传算法NSGAII的综合能源优化调度(Matlab代码实现)
基于非支配排序遗传算法NSGAII的综合能源优化调度(Matlab代码实现)
116 0
基于非支配排序遗传算法NSGAII的综合能源优化调度(Matlab代码实现)
|
12天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】多目标螳螂搜索算法MOMSA与非支配排序的鲸鱼优化算法NSWOA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】多目标螳螂搜索算法MOMSA与非支配排序的鲸鱼优化算法NSWOA求解无人机三维路径规划研究(Matlab代码实现)
|
2月前
|
机器学习/深度学习 算法 安全
【无人机3D路径规划】基于非支配排序遗传算法NSGAII的无人机3D路径规划研究(Matlab代码实现)
【无人机3D路径规划】基于非支配排序遗传算法NSGAII的无人机3D路径规划研究(Matlab代码实现)
132 1
|
19天前
|
机器学习/深度学习 算法 安全
【微电网】【创新点】基于非支配排序的蜣螂优化算法NSDBO求解微电网多目标优化调度研究(Matlab代码实现)
【微电网】【创新点】基于非支配排序的蜣螂优化算法NSDBO求解微电网多目标优化调度研究(Matlab代码实现)
|
2月前
|
机器学习/深度学习 算法 安全
【优化调度】基于matlab非支配排序遗传算法求解车辆充电调度优化问题研究(Matlab代码实现)
【优化调度】基于matlab非支配排序遗传算法求解车辆充电调度优化问题研究(Matlab代码实现)
|
8天前
|
供应链 算法 Java
【柔性作业车间调度问题FJSP】基于非支配排序的多目标小龙虾优化算法求解柔性作业车间调度问题FJSP研究(Matlab代码实现)
【柔性作业车间调度问题FJSP】基于非支配排序的多目标小龙虾优化算法求解柔性作业车间调度问题FJSP研究(Matlab代码实现)
|
13天前
|
存储 算法 搜索推荐
软考算法破壁战:从二分查找到堆排序,九大排序核心速通指南
专攻软考高频算法,深度解析二分查找、堆排序、快速排序核心技巧,对比九大排序算法,配套动画与真题,7天掌握45%分值模块。
70 0
软考算法破壁战:从二分查找到堆排序,九大排序核心速通指南
|
2月前
|
传感器 并行计算 算法
【无人机编队】基于非支配排序遗传算法II NSGA-II高效可行的无人机离线集群仿真研究(Matlab代码实现)
【无人机编队】基于非支配排序遗传算法II NSGA-II高效可行的无人机离线集群仿真研究(Matlab代码实现)
147 3
|
7月前
|
JavaScript 前端开发 算法
JavaScript 中通过Array.sort() 实现多字段排序、排序稳定性、随机排序洗牌算法、优化排序性能,JS中排序算法的使用详解(附实际应用代码)
Array.sort() 是一个功能强大的方法,通过自定义的比较函数,可以处理各种复杂的排序逻辑。无论是简单的数字排序,还是多字段、嵌套对象、分组排序等高级应用,Array.sort() 都能胜任。同时,通过性能优化技巧(如映射排序)和结合其他数组方法(如 reduce),Array.sort() 可以用来实现高效的数据处理逻辑。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~

热门文章

最新文章