1. 贪心算法概述
贪心算法是一种使用贪心思想来解决最优化问题的算法，它通常在一些问题中得到应用，如会场安排、区间选点等问题。贪心算法在每个阶段选择局部最优解，最终得到的结果是全局最优解，然而并非所有的问题都可以使用贪心算法来解决。贪心算法是一种高效的算法，时间复杂度通常为O(nlogn)，其中n为问题规模。
2. 会场安排问题
2.1 问题描述
假设有一个会议室可以用来举办多个会议，每个会议需要用到同一间会议室。现在给出每个会议的开始时间和结束时间，如何安排这些会议，使得会议室的利用率最大？
2.2 解决思路
我们可以按照会议的结束时间来排序，每次选取结束时间最早的会议安排在会议室中，这样可以使得会议室尽可能地空闲出来给其他会议使用。如果当前会议开始时间早于上一个会议的结束时间，那么它们就存在时间上的冲突，需要另外安排会场。使用贪心算法，可以得到会场使用的最小数量。
2.3 代码实现
bool cmp(pair<int,int> a,pair<int,int> b) {
return a.second < b.second;
}
void arrangeMeeting(vector<pair<int,int>> meetings) {
sort(meetings.begin(), meetings.end(), cmp);
int end_time = -1;
int cnt = 0;
for(int i=0; i<meetings.size(); i++) {
if(meetings[i].first >= end_time) {
cnt++;
end_time = meetings[i].second;
}
}
cout << cnt << endl;
}
3. 区间选点问题
3.1 问题描述
假设有多个闭区间，在每个区间内至少放置一个点，如何放置这些点，使得所需点的数量最小？
3.2 解决思路
对于每个闭区间，我们可以选择在区间的右端点放置一个点，这样可以最大限度地覆盖区间。然后对所有区间的右端点进行排序，按顺序选取每个区间的右端点放置一个点。如果下一个区间的左端点小于当前已选中区间的右端点，那么说明这两个区间存在交叉，需要再放置一个点。这样选择的点数量就是最小的。
3.3 代码实现
bool cmp(pair<int,int> a,pair<int,int> b) {
return a.second < b.second;
}
void selectPoints(vector<pair<int,int>> intervals) {
vector<int> res;
sort(intervals.begin(), intervals.end(), cmp);
int end_time = -1;
for(int i=0; i<intervals.size(); i++) {
if(intervals[i].first > end_time) {
res.push_back(intervals[i].second);
end_time = intervals[i].second;
}
}
for(int i=0; i<res.size(); i++) {
cout << res[i] << " ";
}
}
4. 总结
贪心算法是一种常用的解决最优化问题的算法，它通过在每个阶段选择局部最优解，最终得到全局最优解。会场安排问题和区间选点问题是两个典型的贪心算法问题，我们可以通过将问题转化为对起始/结束时间或者区间端点的排序问题，使用贪心算法来解决。
需要注意的是，并非所有问题都可以通过贪心算法来解决，需要根据具体问题来选择使用什么样的算法。同时，在使用贪心算法的过程中，需要确保每个阶段的选择都是局部最优的，并且局部最优的选择最终可以得到全局最优解。