贪心思想

正如其名，贪心，就是贪！

贪心思想简介

• 定义: 贪心算法是一种在每一步都做出局部最优选择的策略，期望通过这些局部最优最终得到全局最优解。
• 应用场景: 适用于可以通过局部最优构建全局最优解的问题，如活动选择问题、最小生成树等。

简单来说，在每一步选择时，只考虑当前的最佳选择，而不考虑未来的决策。

这儿有一个并不完全正确的争议点，即最优子结构，考虑到贪心从全局来看，始终为有限制的局部最优解，一定程度上的确符合最优子结构，但是全局来看并不一定符合。

例如，如果使用贪心解决背包问题，那么优先选择“性价”比最高的物品。但它未必给出最优解。

典型问题

活动选择问题

给定一组活动，每个活动有一个开始时间和结束时间。我们希望安排尽可能多的互不重叠的活动。每次选择活动时，总是选择最早结束的那个活动。

这儿可以使用反证法，若选择的不是最早结束的那么，最早结束的时间肯定比选择的多，。即原本是最优解。最优解为选择最早结束的，选择符合条件的最早结束的合理的继续。

class Solution {
public:
    vector<pair<int, int>> maxActivities(vector<pair<int, int>>& activities) {
        // 按照活动的结束时间进行排序
        sort(activities.begin(), activities.end(), [](pair<int, int>& a, pair<int, int>& b) {
            return a.second < b.second;
        });

        vector<pair<int, int>> result;
        int lastFinishTime = activities[0].second;
        result.push_back(activities[0]);

        for (int i = 1; i < activities.size(); i++) {
            if (activities[i].first >= lastFinishTime) {
                result.push_back(activities[i]);
                lastFinishTime = activities[i].second;
            }
        }

        return result;
    }
};