小红书9月10日机考笔试题与解析

《面试题目》

1. 如何在保持任务顺序的前提下安排连续时隙，使峰值干扰最小？
2. 如何设计状态转移来处理任务之间可留空时隙的情况？
3. 如何证明动态规划转移覆盖了所有合法安排？

《参考解析》

1. 枚举每项任务的可行起始位置，以任务编号和已使用时隙作为状态，转移时合并当前区间最大干扰，取所有方案的最小峰值。
2. 把“留空”视作起点可向后移动，而不是额外插入任务；用前缀最大值或区间最大值优化重复计算。
3. 状态必须包含影响后续决策的全部信息，初始化不可达状态为无穷大，最终在所有合法终点状态中取最优值。