贪心问题，堆和排序是最常用的办法
1. 贪心算法的解题套路
题目1：会议安排问题
- 思路
按会议结束时间排序，依次取出会议结束时间最早的会议
#include<iostream>
#include<queue>
using namespace std;
bool cmp(vector<int> N1,vector<int> N2)
{
return N1[1] > N2[1];
}
int main()
{
int count = 0;
int endtime = 0;
vector<vector<int>> HY = { {11,13},{18,20} ,{12,15},{6,8},{14,17},{7,9},{7,10} };
priority_queue<vector<int>, vector<vector<int>>, decltype(&cmp)> que(cmp);
for (int i = 0; i < HY.size(); i++)
{
que.push(HY[i]);
}
while (!que.empty())
{
vector<int> cur_HY = que.top();
que.pop();
if (endtime < cur_HY[0])
{
count++;
endtime = cur_HY[1];
}
}
cout << count << endl;
return 0;
}
题目2：哈夫曼编码问题
- code
int main()
{
priority_queue<int, vector<int>, greater<int>> que;
int cost = 0;
vector<int> Arr = { 1, 2, 6, 4, 8, 6, 10, 5, 45 };
for (int i = 0; i < Arr.size(); i++)
{
que.push(Arr[i]);
}
while (que.size() > 1)
{
int N1 = que.top();
que.pop();
int N2 = que.top();
que.pop();
int S = N1 + N2;
cost += S;
que.push(S);
}
cout << cost << endl;
return 0;
}
贪心策略题目，coding很简单，主要是思路
