简单贪心

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 定义活动结构体
struct Activity {
    int start;  // 开始时间
    int end;    // 结束时间
};

// 自定义排序规则：按结束时间从小到大排
bool cmp(Activity a, Activity b) {
    return a.end < b.end;  // 结束时间早的排前面
}

int greedy(vector<Activity>& acts) {
    // 第1步：按结束时间排序（贪心的基础）
    sort(acts.begin(), acts.end(), cmp);

    int cnt = 1;            // 选了第1个活动
    int last_end = acts[0].end;  // 记录上一个选中活动的结束时间

    // 第2步：从第2个活动开始遍历
    for (int i = 1; i < acts.size(); i++) {
        // 如果当前活动的开始时间 >= 上一个活动的结束时间
        // 说明不冲突，可以选
        if (acts[i].start >= last_end) {
            cnt++;              // 计数 +1
            last_end = acts[i].end;  // 更新结束时间
        }
        // 否则冲突了，跳过这个活动
    }

    return cnt;  // 返回最多能选多少个活动
}

int main() {
    vector<Activity> acts = {{1,3}, {2,5}, {4,7}, {6,8}, {5,9}};
    cout << "最多能参加 " << greedy(acts) << " 个活动" << endl;
    // 输出: 最多能参加 2 个活动

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findContentChildren(vector<int>& g, vector<int>& s) {
    // g: 孩子的需求（满足度）数组
    // s: 糖果的甜度数组

    // 都从小到大排序
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());

    int child = 0;  // 指向当前要满足的孩子
    int candy = 0;  // 指向当前要分配的糖果
    int count = 0;  // 已满足的孩子数

    // 从需求最小的孩子开始，用甜度最小的糖果尝试满足
    while (child < g.size() && candy < s.size()) {
        if (s[candy] >= g[child]) {
            // 这颗糖果够甜，满足这个孩子
            count++;
            child++;   // 下一个孩子
            candy++;   // 下一颗糖果
        } else {
            // 这颗糖果不够甜，试试下一颗更大的糖果
            candy++;
        }
    }

    return count;
}

int main() {
    vector<int> children = {1, 2, 3};   // 孩子需求
    vector<int> candies = {1, 1};       // 糖果甜度

    cout << "满足 " << findContentChildren(children, candies) << " 个孩子" << endl;
    // 输出: 满足 1 个孩子（只有第一个孩子的需求1可以被糖果1满足）

    vector<int> children2 = {1, 2};
    vector<int> candies2 = {1, 2, 3};
    cout << "满足 " << findContentChildren(children2, candies2) << " 个孩子" << endl;
    // 输出: 满足 2 个孩子

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

bool canJump(vector<int>& nums) {
    int maxReach = 0;  // 目前能到达的最远位置

    for (int i = 0; i < nums.size(); i++) {
        // 如果当前位置已经超过能到达的最远位置，说明走不动了
        if (i > maxReach) return false;

        // 更新最远能到达的位置
        maxReach = max(maxReach, i + nums[i]);
    }

    return true;  // 遍历完了都能走到，说明能到终点
}

int main() {
    vector<int> nums1 = {2, 3, 1, 1, 4};
    cout << (canJump(nums1) ? "能到达" : "不能到达") << endl;
    // 输出: 能到达

    vector<int> nums2 = {3, 2, 1, 0, 4};
    cout << (canJump(nums2) ? "能到达" : "不能到达") << endl;
    // 输出: 不能到达（在位置3卡住了，nums[3]=0）

    return 0;
}