【算法】------区间问题（贪心）

🌹作者:云小逸 📝个人主页:云小逸的主页 📝Github:云小逸的Github 🤟motto:要敢于一个人默默的面对自己，强大自己才是核心。不要等到什么都没有了，才下定决心去做。种一颗树，最好的时间是十年前，其次就是现在！学会自己和解，与过去和解，努力爱自己。==希望春天来之前，我们一起面朝大海，春暖花开！==🤟 👏专栏：C++👏 👏专栏：Java语言👏👏专栏：Linux学习👏 👏专栏：C语言初阶👏👏专栏：数据结构👏👏专栏：备战蓝桥杯👏

文章目录 前言​题目描述输入格式输出格式输入样例输出样例题解​ 最后​​

---

前言

今天我们继续学习算法，备战蓝桥杯，加油。这篇文章写的是区间问题，使用了贪心思想。希望这篇可以有幸帮助到你，码字不易，请多多支持。

——————————————————————————————

​ 题目描述

给定 N 个闭区间 [l,r]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。输出选择的点的最小数量。位于区间端点上的点也算作区间内。

输入格式

第一行包含整数 n n n。

接下来 n n n 行，每行包含两个整数 l i l_i li​ 和 r i r_i ri​。

输出格式

输出一个整数表示答案。

输入样例 3 1 3 2 4 3 5 输出样例 2 题解

这道题是一道经典的区间问题，可以使用贪心算法来解决。

首先将每个区间按右端点从小到大排序。然后每次枚举每个区间，当某个区间内已经取了点时（即当前查看区间的左端点大于当前组的最大右端点），则说明有交集，组数加1，否则组数不变，直接pass，最后输出组数即可。

下面是代码实现：

#include <iostream> #include <algorithm> using namespace std; const int N = 100010; int n; struct Range { int l, r; bool operator< (const Range &W)const // 重载小于号运算符 { return r < W.r; // 按右端点从小到大排序 } }range[N]; int main() { scanf("%d", &n); // 输入区间的个数n for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r); // 输入n个区间的左右端点 sort(range, range + n); // 按照右端点从小到大排序 int res = 0, ed = -2e9; // res表示不相交区间的个数，ed表示当前不相交区间的右端点 for (int i = 0; i < n; i ++ ) if (ed < range[i].l) // 如果当前区间和前面的不相交 { res ++ ; // 不相交区间个数加1 ed = range[i].r; // 更新当前不相交区间的右端点 } printf("%d\n", res); // 输出不相交区间的个数 return 0; } ​ 最后

十分感谢你可以耐着性子把它读完和我可以坚持写到这里，送几句话，对你，也对我：

1.把时间尺度拉长，拉长十年看当下

2.不说负面情绪，只描述事实;

3.越专注于过好自己，能量和幸运越会照顾你； 只解决问题，不做没有意义的担心，输了就认；

4.学会原谅自己，要允许自己做错事,允许自己出现情绪波动，我知道你已经很努力很努力在做好了

5.所有你害怕的、想逃避的事情，最终都要面对，既然这样不如选择坦然面对。即使结果不如人愿，没关系，至少这个过程是享受的，而不是一路带着恐惧和害怕。

​

最后如果觉得我写的还不错，请不要忘记点赞✌，收藏✌，加关注✌哦(｡･ω･｡)

愿我们一起加油，奔向更美好的未来，愿我们从懵懵懂懂的一枚菜鸟逐渐成为大佬。加油，为自己点赞！ ​

​