贪心算法（Greedy Algorithm) 概述：
贪心算法是一种在求解最优化问题时采取的一种常用算法策略。贪心算法的基本思想是，每次选择当前情况下的局部最优解，并相信这个局部最优解能够导致全局最优解。贪心算法通过迭代的方式一步步地构建最优解，并不进行回溯。
贪心算法的一般步骤：
1. 将问题分解成多个子问题；
2. 对每个子问题，确定一个最优解；
3. 对每个子问题的最优解进行合并，得到原问题的最优解。
贪心算法的正确性需要满足两个条件：
1.最优子结构：问题的最优解能够由子问题的最优解组合而成。
2. 贪心选择性：通过局部最优选择能够得到全局最优解。
贪心算法的特点包括：
1. 局部最优：在每一步选择中都采取当前状态下最好或最优的选择。
2. 无后效性：一旦做出选择，此选择就不再改变。
3. 贪心选择性质：一个问题的最优解包含其子问题的最优解。
4. 最优子结构：一个问题的最优解可以通过其子问题的最优解来获得。
贪心算法适用于解决一些特定问题，如：
- 图论中的最短路径问题：如Dijkstra算法和Bellman-Ford算法。
- 最小生成树问题：如Kruskal算法和Prim算法。
- 调度问题：如区间调度问题。
- 压缩编码：如霍夫曼编码。
贪心算法的步骤通常包括：
1. 建立数学模型：定义决策变量、目标函数和约束条件。
2. 寻找贪心选择性质：确定每一步的贪心选择策略。
3. 证明贪心选择的正确性：通过数学归纳法或其他方法证明贪心选择最终能得到问题的最优解。
4. 算法实现：根据贪心选择性质编写算法代码。
需要注意的是，贪心算法并不总是能得到问题的最优解，它适用于那些具有贪心选择性质的问题。在没有贪心选择性质的问题上，贪心算法可能只能得到近似解。
由于贪心是一种思想，没有具体的算法模板，而且贪心一般不会单独作为一种算法出现在题目中，一般会跟其他算法结合在一起出现。例如：动态规划、递归、高级数据结构等。在此基础上保证每一步时最优解的情况下就可以得到最优的答案。下面我们将以例题的形式让大家来了解这种思想。
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
强大的kAc建立了强大的帝国，但人民深受其学霸及23文化的压迫，于是勇敢的鹏决心反抗。
kAc帝国防守森严，鹏带领着小伙伴们躲在城外的草堆叶子中，称为叶子鹏。
kAc帝国的派出的n个看守员都发现了这一问题，第i个人会告诉你在第li个草堆到第ri个草堆里面有人，要求你计算所有草堆中最少的人数，以商议应对。
“你为什么这么厉害”，得到过kAc衷心赞美的你必将全力以赴。
输入格式
第一行一个数字n，接下来2到n+1行，每行两个数li和ri，如题。
输出格式
输出一个数，表示最少人数。
样例输入
5
2 4
1 3
5 7
1 8
8 8
样例输出
3
数据规模和约定
30%的数据n<=10
70%的数据n<=100
100%的数据n<=1000
所有数字均在int表示范围内
贪心算法引入：
这道题是要求得最小的人数，题意类似于区间合并的问题，就是被这个区间被覆盖掉，所选的区间尽量包含士兵口中所说的更多的区间，那么我就要找一个标准，，一般选择一个区间的左端点。为了方便计算，那么我们先要进行排好序， 根据左端点的大小，由小到大排序。排完之后我们就可以以左端点为标准，去查看右端点的情况，如果有右端点不在这个范围里了，那么更新左端点的标准，在这个区间再加上一个人，继续更新，一次类推。
#include<stdio.h> int sum;//最少人数 int a[1005][2];//a[i][0]表示左端点，a[i][1]表示右端点 int vis[1005];//标记数组，若能分层成一组则置为1，最后统计1的个数 int main() { int i, j, x,n; scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d%d", &a[i][0], &a[i][1]);//输入左端点与右端点 } for (i = 0; i < n - 1; i++) {//冒泡排序以右端点为基准（也可以左端点），对每组左右端点排序 for (j = 0; j < n-1-i; j++) { if (a[j][1] > a[j + 1][1]) { int tmp; tmp = a[j][1]; a[j][1] = a[j + 1][1]; a[j + 1][1] = tmp; tmp = a[j][0]; a[j][0] = a[j + 1][0]; a[j + 1][0] = tmp; } } } x = a[0][1];//初始值 vis[0] = 1;//第一个li-ri必然有一个刺客 for (i = 1; i < n; i++) {//对已经排序好的数组，只要i-1的右端点>i的左端点的就另起一个 if (a[i][0] > x) { //标记vis[i]=1；若i-1的右端点<i的左端点就共用一个刺客 vis[i] = 1; //不断更新x，保证刺客最少 x = a[i][1]; } } for (i = 0; i < n; i++) {//统计刺客个数 if (vis[i] == 1) { sum++; } } printf("%d", sum); return 0; }
本人小白一枚，若有不明白的地方，可私信博主，可一一解答；若有错误的地方，恳请大佬指出，共同进步。执笔至此，感触彼多，全文将至，落笔为终，感谢各位的支持。
