知识点指南

Greedy

Greedy solutions repeatedly make the best local choice, but only when there is a reason that this choice cannot harm the final answer.

什么时候使用

读题时可以留意这些信号。

The story naturally suggests earliest, smallest, cheapest, or largest choice.
After sorting, each accepted choice leaves the most room for the future.
You can explain why replacing the greedy choice never improves the answer.

常见错误

提交前可以检查这些小陷阱。

Using a greedy rule that only works on samples.
Forgetting the sort step.
Updating state even when the candidate was not accepted.

怎么写成代码

把知识点翻译成变量、循环、判断和更新。

Sort if the choice depends on order.
Keep the current resource, boundary, or last chosen item.
Scan candidates once and accept a candidate when it fits.
Update the boundary/resource immediately after accepting.

在 Block 题里长什么样

答题时通常会看到这些步骤被拆成代码块。

1Read candidates.
2Sort by the greedy key.
3Initialise answer and current boundary.
4Loop through candidates.
5If candidate is compatible, take it.
6Update answer and boundary.

题目里怎么出现

读题时先找这些信号，再决定答案区应该选哪些 blocks。

The task asks for maximum number of non-overlapping items or minimum resources.
Choosing the earliest finishing/cheapest/smallest valid option leaves future options open.
Backtracking sounds possible but should not be necessary.

Take compatible intervals

一个小型模板，展示代码和 blocks 的对应关系。

C++

sort(intervals.begin(), intervals.end(), byEnd);
int answer = 0, lastEnd = -1;
for (auto [start, end] : intervals) {
    if (start >= lastEnd) {
        answer++;
        lastEnd = end;
    }
}
cout << answer << '\n';

Python

intervals.sort(key=lambda x: x[1])
answer = 0
last_end = -1
for start, end in intervals:
    if start >= last_end:
        answer += 1
        last_end = end
print(answer)

对应 block 顺序

1Read intervals.
2Sort by ending time.
3Initialise chosen count and last end.
4Loop through intervals.
5Take interval if compatible.
6Update last end.