1
// N 种任务，同种任务之间必须有 n 个单位的冷却
2
// 求最短执行时间
3
// 贪心：按频率降序排列，高频任务之间插入冷却槽
4
int leastInterval(std::vector<char>& tasks, int n) {
5
    std::vector<int> freq(26, 0);
6
    for (char t : tasks) freq[t - 'A']++;
7
    std::sort(freq.begin(), freq.end(), std::greater<int>());
8

9
    int maxFreq = freq[0];
10
    int idleSlots = (maxFreq - 1) * n;          // 冷却槽总数
11

12
    // 用次高频任务填充冷却槽
13
    for (int i = 1; i < 26 && freq[i] > 0; ++i) {
14
        idleSlots -= std::min(freq[i], maxFreq - 1);
15
    }
16

17
    idleSlots = std::max(0, idleSlots);
18
    return tasks.size() + idleSlots;
19
}

1
#include <queue>
2
#include <string>
3
#include <unordered_map>
4

5
struct HuffmanNode {
6
    char ch;
7
    int  freq;
8
    HuffmanNode *left, *right;
9

10
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
11
    HuffmanNode(char c, int f, HuffmanNode* l, HuffmanNode* r)
12
        : ch(c), freq(f), left(l), right(r) {}
13
};
14

15
// 构建霍夫曼树，返回每个字符的编码
16
std::unordered_map<char, std::string> buildHuffman(
17
    const std::unordered_map<char, int>& freqMap) {
18

19
    // 最小堆，按频率排序
20
    auto cmp = [](HuffmanNode* a, HuffmanNode* b) {
21
        return a->freq > b->freq;  // 频率小的优先
22
    };
23
    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, decltype(cmp)> pq(cmp);
24

25
    for (auto& [ch, freq] : freqMap) {
26
        pq.push(new HuffmanNode(ch, freq));
27
    }
28

29
    // 贪心：每次合并频率最小的两个
30
    while (pq.size() > 1) {
31
        auto* left = pq.top(); pq.pop();
32
        auto* right = pq.top(); pq.pop();
33

34
        auto* parent = new HuffmanNode('\0',
35
            left->freq + right->freq, left, right);
36
        pq.push(parent);
37
    }
38

39
    // DFS 遍历树，生成编码
40
    std::unordered_map<char, std::string> codes;
41
    std::function<void(HuffmanNode*, std::string)> dfs =
42
        [&](HuffmanNode* node, std::string code) {
43
        if (!node) return;
44
        if (!node->left && !node->right) {  // 叶子节点
45
            codes[node->ch] = code;
46
        }
47
        dfs(node->left,  code + "0");
48
        dfs(node->right, code + "1");
49
    };
50

51
    dfs(pq.top(), "");
52
    return codes;
53
}

1
// 贪心：记录每个字符最后出现的位置
2
// 遍历时不断扩展当前片段的右边界
3
std::vector<int> partitionLabels(std::string s) {
4
    std::vector<int> last(26, 0);
5
    for (int i = 0; i < s.size(); ++i) {
6
        last[s[i] - 'a'] = i;
7
    }
8

9
    std::vector<int> result;
10
    int start = 0, end = 0;
11

12
    for (int i = 0; i < s.size(); ++i) {
13
        end = std::max(end, last[s[i] - 'a']);  // 扩展右边界
14
        if (i == end) {                          // 到达当前片段的边界
15
            result.push_back(i - start + 1);
16
            start = i + 1;
17
        }
18
    }
19
    return result;
20
}

1
// people[i] = [h, k]，h 是身高，k 是前面有 k 个身高 ≥ h 的人
2
// 贪心：先按身高降序排，身高相同按 k 升序排
3
// 然后逐个插入：k 就是在当前结果中的插入位置
4
std::vector<std::vector<int>> reconstructQueue(
5
    std::vector<std::vector<int>>& people) {
6

7
    std::sort(people.begin(), people.end(),
8
        [](const auto& a, const auto& b) {
9
            return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
10
        });
11

12
    std::vector<std::vector<int>> result;
13
    for (const auto& p : people) {
14
        result.insert(result.begin() + p[1], p);
15
    }
16
    return result;
17
}

1
// 玩家有 N 个技能，每个技能有冷却时间 [start, end)
2
// 不能同时使用有 CD 重叠的技能，求最多能释放多少个技能
3
// → 标准区间调度问题
4
struct Skill {
5
    std::string name;
6
    int         cooldownStart;
7
    int         cooldownEnd;    // 冷却结束时间
8
};
9

10
std::vector<Skill> maxSkillsInWindow(const std::vector<Skill>& skills) {
11
    auto sorted = skills;
12
    std::sort(sorted.begin(), sorted.end(),
13
        [](const Skill& a, const Skill& b) {
14
            return a.cooldownEnd < b.cooldownEnd;
15
        });
16

17
    std::vector<Skill> result;
18
    int lastEnd = -1;
19

20
    for (const auto& skill : sorted) {
21
        if (skill.cooldownStart >= lastEnd) {
22
            result.push_back(skill);
23
            lastEnd = skill.cooldownEnd;
24
        }
25
    }
26
    return result;
27
}

1
// 多个 Buff 道具，每个提供 [start, end) 的属性加成
2
// 选一组互不重叠的 Buff，使总加成最大
3
// 这是"带权区间调度"——经典 DP 问题（贪心不适用！）
4
// 但可以先贪心排序，再 DP
5
struct Buff {
6
    int start, end, value;
7
};
8

9
int maxBuffValue(std::vector<Buff>& buffs) {
10
    std::sort(buffs.begin(), buffs.end(),
11
        [](const Buff& a, const Buff& b) { return a.end < b.end; });
12

13
    int n = buffs.size();
14
    std::vector<int> dp(n, 0);
15

16
    for (int i = 0; i < n; ++i) {
17
        dp[i] = buffs[i].value;
18

19
        // 二分查找最后一个不重叠的 Buff
20
        int lo = 0, hi = i - 1, last = -1;
21
        while (lo <= hi) {
22
            int mid = (lo + hi) / 2;
23
            if (buffs[mid].end <= buffs[i].start) {
24
                last = mid;
25
                lo = mid + 1;
26
            } else {
27
                hi = mid - 1;
28
            }
29
        }
30

31
        if (last != -1) dp[i] = std::max(dp[i], dp[last] + buffs[i].value);
32
        if (i > 0) dp[i] = std::max(dp[i], dp[i - 1]);
33
    }
34
    return dp[n - 1];
35
}

1
// N 个资源点排成环形，采集需要消耗燃料
2
// 找一个起点使得能绕一圈采集完所有资源
3
// → 标准加油站问题
4
struct ResourceNode {
5
    int fuelGain;     // 采集获得燃料
6
    int fuelCost;     // 去下一个点的消耗
7
};
8

9
int findStartNode(const std::vector<ResourceNode>& nodes) {
10
    int n = nodes.size();
11
    int totalSurplus = 0, currentSurplus = 0, start = 0;
12

13
    for (int i = 0; i < n; ++i) {
14
        int diff = nodes[i].fuelGain - nodes[i].fuelCost;
15
        totalSurplus += diff;
16
        currentSurplus += diff;
17

18
        if (currentSurplus < 0) {
19
            start = i + 1;
20
            currentSurplus = 0;
21
        }
22
    }
23
    return totalSurplus >= 0 ? start : -1;
24
}

1
// 游戏主循环中，不同类型任务有冷却时间
2
// 同类任务必须间隔 n 帧 → 求最短帧数完成所有任务
3
int minFrames(const std::vector<int>& taskTypes, int n) {
4
    // 实现同 LeetCode 621 任务调度器
5
    std::unordered_map<int, int> freq;
6
    for (int type : taskTypes) freq[type]++;
7

8
    int maxFreq = 0;
9
    for (auto& [_, f] : freq) maxFreq = std::max(maxFreq, f);
10

11
    int maxCount = 0;
12
    for (auto& [_, f] : freq) {
13
        if (f == maxFreq) ++maxCount;
14
    }
15

16
    int frameCount = (maxFreq - 1) * (n + 1) + maxCount;
17
    return std::max(frameCount, (int)taskTypes.size());
18
}