贪心算法（又称贪婪算法）是指:不从整体最优上加以考虑，做出的是在某种意义上的局部最优解。

例1: 硬币问题

🍎🍎有1元、5元、10元、50元、100元、500元的硬币各C1、C2、C3、C4、C5、C6枚，现在要用这些硬币来支付A元，问：最少需要多少枚硬币？本题目假设至少存在一种解决方案。 →样例输入：（前6项为各种面值的硬币数量、最后一个数字为需要支付的钱） 3 2 1 3 0 2 620 →样例输出： 6

思路:优先使用大面值硬币。

for (int i = b.length - 1; i >= 0; i–)

  1. 尽可能多地使用面值为500元的硬币
  2. 再尽可能多地使用面值为100元的硬币
  3. 再尽可能多地使用面值为50元的硬币
  4. 再尽可能多地使用面值为10元的硬币
  5. 再尽可能多地使用面值为5元的硬币
  6. 再尽可能多地使用面值为1元的硬币
#include<iostream>

using namespace std;

int main()
{
	int coin[6]={1,5,10,50,100,500};//数组coin存储硬币面值
	int a[6];//数组a存储各种硬币数量
	int A;//sum表示待支付金钱 
	int sum=0;	
	for(int i=0;i<6;i++)
	{
		cin>>a[i];
	}
	cin>>A;
	for(int i=5;i>=0;i--)
	{
		int t=min(A/coin[i],a[i]);//用t存储各个硬币的使用数量
		A=A-t*coin[i];
		sum+=t;		
	}
	cout<<sum<<endl;;
	return 0;
}
**例2:区间问题** 🍌🍌有n项工作，每项工作分别在s[i]时间开始、在t[i]时间结束。对于每项工作你都可以选择参加与否。如果选择了参与，那么自始至终都必须全程参与。此外，参与工作的时间段不能重叠（即参与该项目的时间内不能参加别的项目）。如图所示：

你的目标是参与尽可能多的工作，那么最多能参与多少项工作呢？ 限制条件：1<= N <= 100000 1 <= <= <=1e9

样例输入：（输入顺序为n（n个时间段）、n个开始时间、n个结束时间）
5
1 2 4 6 8
3 5 7 9 10
样例输出：
3

这个问题可以用贪心算法来解决，可以设计出各种各样的策略，例如：
1.在可选工作中，每次都选取开始时间最早的工作；
2.在可选工作中，每次都选取结束时间最早的工作；
3.在可选工作中，每次都选择用时最短的工作。
这些策略都是很容易想的到的、但是并不是全部策略都是能解决问题的。
策略1的反例：

策略3的反例：

只有策略二是正确的,即每次都选择结束时间最早的时间段。

#include<iostream>
#include<algorithm>

using namespace std;

struct node{
	int s;
	int t;
}time[10000];

//bool cmp(node a,node b)
//{
// if(a.t!=b.t) return a.t<b.t; //如果a.t != b.t 小的在前 
// else return a.s<b.s;
//}

bool cmp(node a,node b)
{//sort函数的结构体排序,从小到大 
	if(a.s<b.s)
	{
		return true;
	}
	else
		if(a.s==b.s)
		{
			if(a.t<b.t)
			{
				return true ;
			}
		}
	return false ;
}

int main()
{

	int n;
	cin >> n;
	for(int i=0;i<n;i++)
	{
		cin >> time[i].s;		
	 } 
	for(int i=0;i<n;i++)
	{
		cin >> time[i].t;		
	}
	sort(time,time+n,cmp);
	int sum=0;//sum用来计数 
	int t=0;//t存储工作结束时间 
	for(int i=0;i<n;i++)
	{
		if(t<time[i].s)		//如果当前工作结束时间小于下一个工作开始时间 
		{
			t=time[i].t;	//更新时间t 
			sum++;		//计数器++ 
		}
	}
	cout << sum << endl; 
	return 0;
}