外观
02 - 先别急着写代码:如何把业务问题抽象成算法模型
前置阅读:01 - 时间复杂度如何决定系统上限。
本文负责问题建模;贪心选择的完整证明见20 - 贪心算法与正确性证明,测试方法见A - 算法正确性、测试与基准方法。
摘要
“安排尽可能多的任务”看似明确,却没有说明首尾相接算不算冲突、任务能否中断、是否要考虑收益。这些条件会改变合法答案,甚至改变算法选择。本文以单机任务调度为例,先把业务规则写成输入、输出和约束,再解释如何选择算法并检查实现。
1. 场景:一句“安排最多任务”藏着多少条件
产品提出需求:一台机器每天有多个任务申请,请安排尽可能多的任务。每个任务有开始和结束时间,执行期间不能重叠。
编码前至少要确认:
- 时间区间是
[start, end)还是闭区间? - 任务能否中断?
- 目标是任务数量最多,还是收益最大?
- 输入是否已排序?
- 相同时间任务如何处理?
半开区间 [start, end) 表示包含开始时刻、不包含结束时刻。因此 [1,4) 与 [4,6) 可以接续执行;若使用闭区间,两者在时刻 4 有交集,冲突判断就要改变。
下文先讨论固定起止时间、任务具有正执行时长(start < end)、不可拆分或中断、只有一台机器、没有前置依赖的情况,使用半开区间,目标是任务数量最多。本文的贪心策略、不变量和暴力基线说明都以这些条件为前提。零时长任务 [t,t) 是空区间,不在当前论证范围内;原代码仍允许这种输入,其业务语义及算法处理是否符合预期留待核验,详见第 6 节。
输入不要求预先排序,相同起止时间的申请仍作为不同任务记录处理。“数量最多”只计算完成了几个任务;“收益最大”则要累加每个任务的收益,即使选择数量更少,也可能更划算。
这些规则构成算法模型:保留影响答案的数据和关系,把业务描述变成可计算、可检查的问题。当前数量目标可以尝试按结束时间排序的贪心算法;改成收益目标后通常需要动态规划。贪心是每一步作出当前最有利的选择,动态规划则通过保存子问题的最优结果来求解更大的问题。为什么本例允许贪心,第 4 节再解释。
2. 五步抽象法
第一步:定义输入与输出
先明确“算法收到什么、必须交付什么”。本例把每个任务表示为起止时间,业务需要的完整输出是一组被选中的任务:
text
输入:n 个区间 (start, end)
输出:一组互不重叠的区间
目标:选择数量最大目标函数是评价合法方案好坏的计算规则。本例的目标函数是“所选任务的数量”,要使它最大。后文代码只返回最大数量,用来演示选择过程;若接口需要具体排期,还要记录选中的任务及其业务标识。只返回数量并不等于交付了完整排期。
第二步:列出约束
约束要同时覆盖业务规则和资源限制。业务上必须保持单机、不可中断、半开区间及正时长(start < end)等条件;实现上还要确认任务数 n 的上限、时间值范围,以及是否允许改变输入数组的顺序。正时长是当前模型的前提,不代表原代码已经检查了这个条件。
数据规模用于筛选候选算法。n <= 20 可以考虑枚举,因为所有子集的数量是 2^n;n = 100000 时,枚举通常不可行,应优先考虑 O(n log n) 或更低的方案。这是工作量估算,能否满足接口延迟和内存限制还要结合实现与运行环境测量。
第三步:写出业务不变量
不变量是算法执行过程中始终保持成立的性质。本例要求已选择的任务彼此不重叠。在上述正时长模型中,按结束时间从早到晚扫描,用 lastEnd 保存上一个已选任务的结束时间;要把新任务接在已选任务之后,必须满足 start >= lastEnd。这个接续条件不能直接推广到零时长空区间。
加入任务前,已有任务互不冲突;满足这个条件的新任务又在已有任务之后开始,因此加入后仍不冲突。这个解释说明方案合法,但还不能说明数量最多:合法性回答“能不能这样安排”,最优性回答“有没有更好的安排”。
第四步:先写正确的暴力基线
暴力基线是不依赖优化技巧、直接检查所有候选的参考实现。每个任务都有“选或不选”两种选择,所以共有 2^n 个子集。在当前正时长、半开区间模型下,逐个检查是否冲突,再取合法子集中的最大任务数,就能得到小规模输入的参考答案。第 6 节按开始时间排序后检查相邻任务的做法,也在这个范围内作为基线;零时长输入的处理仍待核验。
O(2^n) 描述的是候选数量,还要计入每个子集的构造和检查成本。第 6 节的实现会对子集排序,总时间上界为 O(2^n · n log n)。它不适合大规模排期,但可以与优化算法比较结果;比较之前仍需确认两者使用相同的冲突规则。
第五步:识别问题结构
这里是区间选择问题:从一组时间区间中选择数量最多的互不冲突区间。对于当前还能接续的任务,结束越早,后续任务就越早可以开始。因此可以先按结束时间排序,依次选择不冲突的任务。这个直觉只是候选策略,仍需证明它不会排除最优答案。
3. 最小实现
下面是 Java 17 的类定义,展示核心方法,没有 main 运行入口。record Task 用于保存两个整数时间值,Task::end 表示按任务的结束时间比较。方法的讲解假设数组及元素非 null、任务满足 start < end,但代码本身不检查这些前提,并直接排序调用方的数组;完整示例会先复制数组。
java
import java.util.Arrays;
import java.util.Comparator;
/**
* 可运行示例:先别急着写代码:如何把业务问题抽象成算法模型。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class TaskScheduler {
record Task(int start, int end) {}
static int maxTasks(Task[] tasks) {
Arrays.sort(tasks, Comparator.comparingInt(Task::end));
int count = 0;
int lastEnd = Integer.MIN_VALUE;
for (Task task : tasks) {
if (task.start() >= lastEnd) {
count++;
lastEnd = task.end();
}
}
return count;
}
}count 记录已选数量,lastEnd 记录下一个任务最早可以开始的时刻。初始值 Integer.MIN_VALUE 是 Java int 的最小值,使第一个任务不因缺少前驱而被拒绝。选择任务后更新 lastEnd,跳过任务时保持状态不变。空数组返回 0。
按整数比较为常数成本分析,排序为 O(n log n),扫描为 O(n),整体时间复杂度为 O(n log n)。这表示工作量的增长趋势,不是实际耗时记录。
4. 为什么当前模型允许贪心
先看有正执行时长的任务。假设最优方案的第一个任务是 A,贪心选择的最早结束任务是 G。因为 G.end <= A.end,原方案中所有能接在 A 后面的任务,也都能接在 G 后面。把 A 换成 G,任务数没有减少,后续任务也仍然合法。
于是至少存在一个以 G 开头的最优方案。选定 G 后,只需处理开始时间不早于 G.end 的剩余任务,剩余问题仍有同样的规则,可以继续使用同一理由。这种通过替换说明选择不损失最优答案的方法叫交换论证。
证明依赖“目标是任务数量最多、任务不可拆分、单资源、半开区间”等约束。完整交换论证,以及 Huffman 编码(构造前缀编码的另一类贪心问题)等案例,见贪心算法与正确性证明。
如果目标变成收益最大,上述替换不再成立:一个结束稍晚但收益很高的任务可能更值得选。
5. 反例:看到关键词就套模板
“最多”不一定是贪心,“连续”不一定是滑动窗口,“最短路径”也不一定能用 Dijkstra。滑动窗口通过移动连续范围的边界维护候选,是否适用取决于范围内的信息能否有效维护;Dijkstra 是最短路径算法,标准形式要求边权非负。业务关键词只提示可能的方向,约束才决定能否使用。
6. 完整可运行示例:贪心与暴力基线互相校验
下面是完整类 TaskSchedulingDemo,对应文件名为 TaskSchedulingDemo.java,使用 Java 17,main 提供运行入口。两种方法都假设输入数组及元素非 null;构造器拒绝 start > end,但仍允许 start == end。
零时长任务的语义待核验:[t,t) 是空区间,不能直接套用上面针对正时长任务的论证。原代码的排序和相邻冲突检查是否覆盖业务期望,需要单独验证,不能把构造器接受输入等同于算法对此边界正确。这里保留代码行为,以下推演使用原有的正时长样例。
java
import java.util.Arrays;
import java.util.Comparator;
/**
* 可运行示例:先别急着写代码:如何把业务问题抽象成算法模型。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class TaskSchedulingDemo {
record Task(int start, int end) {
Task {
if (start > end) throw new IllegalArgumentException("start > end");
}
}
static int greedy(Task[] input) {
// 复制输入,避免排序改变调用方持有的原数组。
Task[] tasks = Arrays.copyOf(input, input.length);
// 贪心选择:结束越早,留给后续任务的时间越多。
Arrays.sort(tasks, Comparator.comparingInt(Task::end));
int count = 0;
// lastEnd 表示已选任务中最后一个任务的结束时刻。
int lastEnd = Integer.MIN_VALUE;
for (Task task : tasks) {
// 使用半开区间 [start, end),首尾相接不算冲突。
if (task.start() >= lastEnd) {
count++;
// 一旦选择任务,后续任务必须从它结束后开始。
lastEnd = task.end();
}
}
return count;
}
static int bruteForce(Task[] tasks) {
// int 位掩码只能安全覆盖较小规模;暴力算法本来也只用于校验。
if (tasks.length >= 31) {
throw new IllegalArgumentException("暴力校验只用于小规模输入");
}
int best = 0;
// mask 的第 i 位为 1,表示选中第 i 个任务。
for (int mask = 0; mask < 1 << tasks.length; mask++) {
Task[] selected = new Task[Integer.bitCount(mask)];
int index = 0;
for (int i = 0; i < tasks.length; i++) {
if ((mask & (1 << i)) != 0) selected[index++] = tasks[i];
}
// 排序后只需检查相邻任务,就能判断整个集合是否冲突。
Arrays.sort(selected, Comparator.comparingInt(Task::start));
boolean valid = true;
for (int i = 1; i < selected.length; i++) {
if (selected[i].start() < selected[i - 1].end()) {
valid = false;
break;
}
}
if (valid) best = Math.max(best, selected.length);
}
return best;
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
Task[] tasks = {
new Task(1, 4),
new Task(3, 5),
new Task(0, 6),
new Task(5, 7),
new Task(8, 9),
new Task(5, 9),
};
System.out.println("greedy = " + greedy(tasks));
System.out.println("brute = " + bruteForce(tasks));
}
}greedy() 先复制数组,因此不会改变原数组顺序。bruteForce() 用整数的二进制位表示一个子集,这叫位掩码:第 i 位为 1 就选中第 i 个任务;Integer.bitCount(mask) 计算选中了几个任务。它按开始时间排序,再检查相邻任务,寻找合法子集的最大数量。
贪心为 O(n log n),暴力基线为 O(2^n · n log n)。代码在 n >= 31 时拒绝暴力校验,是为了限制 int 位掩码的范围;这不表示 n = 30 在实际时间预算内可行。贪心复制数组需要 O(n) 额外空间,暴力枚举也会反复创建子集数组。
手工推演
输入任务为 [1,4)、[3,5)、[0,6)、[5,7)、[8,9)、[5,9)。按结束时间排序后:
- 选择
[1,4),此时lastEnd=4; [3,5)与当前任务冲突,跳过;[0,6)同样冲突,跳过;[5,7)满足start >= 4,选择并更新lastEnd=7;[8,9)满足start >= 7,选择并更新lastEnd=9;[5,9)的开始时间小于9,跳过,最终得到 3 个任务。
按这组输入手工推演,程序的预期输出为 greedy = 3 和 brute = 3。
这里真正需要记住的不是排序 API,而是 lastEnd 的含义:它把“已经选择的全部任务”压缩成了判断下一个任务所需的最小状态。
什么时候不能使用这个贪心
- 目标是总收益最大,而不是任务数量最多;
- 任务允许拆分或中断;
- 不同任务需要不同机器或资源;
- 任务之间还有前置依赖。
这些条件改变后,要重新建模,不能沿用当前证明。带收益的固定区间选择可以考虑加权区间动态规划,即比较“选当前任务后的收益”和“不选它的收益”。更复杂的资源和依赖条件还可能涉及流算法(以网络中的流量表达分配)、图算法(以节点和边表达关系)或整数规划(在整数决策变量和约束下优化目标);具体选择取决于完整规则,这些方法并不与上面的条件逐项对应。
7. 容易踩的坑
- 没确认区间开闭、零时长和相同时间任务的语义,冲突判断可能与需求不一致。
- 忽略空输入、非法区间和整数溢出。空数组与
null不同;最小实现不检查区间,完整示例也只拒绝start > end。 - 没核对暴力基线的规则就把它当作标准答案;两个实现也可能共享错误假设。
- 把数量最大替换成收益最大,或把输出排期简化成只返回数量,却没有调整接口契约。
8. 进阶:用差分测试验证算法
差分测试是让不同实现处理同一输入,再比较结果。本例可对小规模随机任务同时计算贪心结果和暴力结果;若数量不同,就保留输入并逐步检查排序、冲突判断和 lastEnd 的更新过程。这能帮助发现错误,但有限样例的一致不能替代正确性证明。
测试应输出随机种子和失败输入,保证问题可以重放。随机种子是伪随机数生成器的初始状态;固定种子并保持生成方式一致,才能重建同一批数据。除随机输入外,还应单独覆盖空数组、首尾相接、同起止时间和零时长任务,并先明确它们的预期语义。
当前方法只返回数量,测试比较这个最优值即可;如果以后返回具体排期,还要检查合法性。存在多个最优方案时,不应要求两个实现返回完全相同的任务集合。完整方法见算法正确性、测试与基准方法。
9. 总结
算法建模的核心,是把模糊业务语言转换为精确的输入、约束、目标和不变量。
- 先确认目标函数,数量最大与收益最大可能需要完全不同的算法。
- 暴力解法不仅是低效方案,也是验证优化实现的正确性基线。
- 模板只能复用结构,不能替代对约束和正确性的分析。
下一篇建议先阅读:算法正确性、测试与基准方法。进入数据结构主线时继续阅读数组与链表的真实取舍。