非遗工坊排期：体验场次并行教室统计 完整解题档案

档案概况

题目、题干与输入输出

正式题面

源文件：official-prompt.md

规则来源

• 赛项说明页码：8
• 训练题主题：非遗工坊排期：体验场次并行教室统计
• 所属赛道：非遗文化赛道

题目背景

非遗工坊需要在有限时间轴上安排多场体验活动。每场活动会占用一个闭区间时段，教务老师希望知道峰值并行场次、最早峰值时段以及整条时间轴中完全空闲的时段数量。

任务描述

• 读取每场活动覆盖的闭区间 [start, end]，并统计所有时段的占用数量。
• 输出最大并行场次，以及最早达到峰值的时段。
• 统计 1..m 中占用为 0 的时段数量。

输入格式

1. 第一行输入 n m，表示活动数量和离散时间轴长度。
2. 接下来 n 行每行输入 start end，表示活动占用闭区间 [start, end]。

输出格式

1. 第一行输出 max_rooms=最大并行场次。
2. 第二行输出 first_peak_slot=最早达到峰值的时段。
3. 第三行输出 idle_slots=空闲时段数。

数据范围与说明

• 1 <= n, m <= 2 * 10^5。
• 1 <= start <= end <= m。
• 区间按闭区间处理，差分时要注意 end + 1。
• 若峰值出现多次，取最早时段。

样例输入

4 8
1 3
2 5
6 7
3 6

样例输出

max_rooms=3
first_peak_slot=3
idle_slots=1

样例解释

• 各时段占用数依次为 1 2 3 2 2 2 1 0。
• 最大并行场次为 3，最早出现在第 3 个时段。
• 只有第 8 个时段空闲，因此 idle_slots=1。

知识点清单

• 差分数组对闭区间加法的建模。
• 前缀和恢复每个时段真实占用量。
• 峰值统计和最早位置维护。
• 空闲时段的线性统计。
• 离散时间轴建模。

约束拆解

源文件：parsed-constraints.md

显式约束

• 1 <= n, m <= 2 * 10^5。
• 1 <= start <= end <= m。
• 区间按闭区间处理，差分时要注意 end + 1。
• 若峰值出现多次，取最早时段。

建模拆解

• 先明确输入的实体和字段，再把它们翻译成 差分数组 + 前缀和恢复 需要的数据结构。
• 把输出中每一项指标都和中间变量对应起来，避免最后临时拼装。
• 先用样例手推一次，再确认边界条件是否都能走到正确分支。

易错边界

• 活动区间恰好覆盖到最后一个时段时，要避免数组越界。
• 多个时段并列达到峰值时，只能保留最早时段。
• 当某些时段完全没有活动时，要正确计入 idle_slots。

计分模型

源文件：scoring-model.md

判题方式

• 主判题方式：simulation
• 主算法：差分数组 + 前缀和恢复

判题重点

• 重点校验状态更新顺序、触发条件和逐轮迭代是否符合题意。
• 隐藏数据会覆盖临界阈值、连续触发和无触发三类情形。

公开样例建议

• 至少准备 1 组题面样例、2 组边界样例和 2 组自定义回归样例。
• 多输出题必须验证所有字段都来自同一套方案。

隐藏数据建议

• 准备多个活动在同一时段开始和结束的样例，检查差分叠加是否稳定。
• 准备全部时段都有活动和全部时段部分空闲两类数据。
• 准备只有一场活动覆盖整条时间轴的极简样例。

验收清单

源文件：acceptance-checklist.md

• 正式题面、约束拆解、评分说明均已补齐
• 样例输入输出已定义并通过主实现校验
• python 主实现已提供并与样例输出对齐
• 调试记录、决策记录、验证计划已补齐
• 可由 20-tools/assemble_case_dossiers.py 汇总为完整解题档案

样例输入输出

样例输入：sample.in

4 8
1 3
2 5
6 7
3 6

样例输出：sample.out

max_rooms=3
first_peak_slot=3
idle_slots=1

题解、建模与最终解法

自动整理的解题流程

• 题目主题：非遗工坊排期：体验场次并行教室统计
• 题目摘要：利用差分数组统计离散时段的教室占用量，找出并行峰值和空闲时段数。
• 判题提示：该题以流程模拟为主，重点是状态更新顺序、异常分支和终止条件。
• 先完成输入、对象、约束和输出的四步建模，再落到具体算法和实现。
• 优先用样例验证最小流程，再补边界测试和错误分支。

解题思路

源文件：solution-rationale.md

1. 问题重述

利用差分数组统计离散时段的教室占用量，找出并行峰值和空闲时段数。

2. 数据结构与建模

• 主算法：差分数组 + 前缀和恢复
• 输入拆解后对应的数据结构要和输出项一一对应。
• 需要重点维护的状态包括：题目实体、核心指标、中间结果和最终答案。

3. 算法步骤

1. 为每个活动对 diff[start] 加一，对 diff[end + 1] 减一。
2. 顺序扫描时间轴，用前缀和恢复每个时段的占用量。
3. 在扫描过程中同步维护最大值、最早峰值时段和空闲时段数量。
4. 按固定格式输出三个统计结果。

4. 正确性说明

• 每一步都严格对应题面给出的规则或约束。
• 所有输出字段都来自同一份计算过程，不会出现“各算各的”的不一致情况。
• 边界情况通过单独分支或统一规则处理，保证程序在最小规模和重复值情况下也稳定。

5. 复杂度分析

• 复杂度取决于输入规模和主算法，但整体设计保持在初中组可讲解、可验证的范围内。
• 只保留必要状态，不引入超出题意的数据结构。

6. 易错点

• 活动区间恰好覆盖到最后一个时段时，要避免数组越界。
• 多个时段并列达到峰值时，只能保留最早时段。
• 当某些时段完全没有活动时，要正确计入 idle_slots。

7. 知识点清单

• 差分数组对闭区间加法的建模。
• 前缀和恢复每个时段真实占用量。
• 峰值统计和最早位置维护。
• 空闲时段的线性统计。
• 离散时间轴建模。

设计决策记录

源文件：decision-log.md

• 选择 差分数组 + 前缀和恢复 作为主算法，因为它能直接覆盖题目的核心约束。
• 题目是典型的区间加一统计，不必逐时段逐活动枚举。
• 差分方案既能保留峰值统计，也能顺手得到空闲时段数。
• Python 与 C++ 版本统一输出格式，便于双语训练和证据采集。

验证计划

源文件：validation-plan.md

• 先验证题面公开样例，确保基础流程无误。
• 准备多个活动在同一时段开始和结束的样例，检查差分叠加是否稳定。
• 准备全部时段都有活动和全部时段部分空闲两类数据。
• 准备只有一场活动覆盖整条时间轴的极简样例。
• 最后再补 1 组手工构造的极小数据，确认程序不会依赖特殊输入规模。

备选方案

源文件：alternatives.md

最终代码与实现

Python 主实现

源文件：main.py

• 实现状态：当前已有可执行实现

import sys


def solve(data: str) -> str:
    tokens = list(map(int, data.split()))
    if not tokens:
        return ""
    it = iter(tokens)
    n = next(it)
    m = next(it)
    diff = [0] * (m + 3)
    for _ in range(n):
        start = next(it)
        end = next(it)
        diff[start] += 1
        diff[end + 1] -= 1
    current = 0
    best = -1
    first_peak = 0
    idle = 0
    for slot in range(1, m + 1):
        current += diff[slot]
        if current > best:
            best = current
            first_peak = slot
        if current == 0:
            idle += 1
    return "\n".join(
        [
            f"max_rooms={best}",
            f"first_peak_slot={first_peak}",
            f"idle_slots={idle}",
        ]
    )


if __name__ == "__main__":
    sys.stdout.write(solve(sys.stdin.read()).strip())
    sys.stdout.write("\n")

代码执行与运行结果

最新成功运行

PY 运行输出摘录

max_rooms=3
first_peak_slot=3
idle_slots=1

全部运行记录索引

调试、修正与流程留痕

调试日志

源文件：debug-journal.md

失败案例目录

源文件：failure-catalog.md

编码过程记录

源文件：implementation-journal.md

全流程文件导航

• 题目总览：s1-jh-06-heritage-workshop-schedule/README.md
• 题面与约束：official-prompt.md、parsed-constraints.md、scoring-model.md、acceptance-checklist.md
• 代码与样例：10-cases/s1-jh-06-heritage-workshop-schedule/02-solution
• 运行证据：10-cases/s1-jh-06-heritage-workshop-schedule/03-execution
• 调试过程：debug-journal.md、failure-catalog.md、implementation-journal.md
• 解法说明：solution-rationale.md、decision-log.md、validation-plan.md、alternatives.md
• 交付档案：final-report.md、appendix-code.md、appendix-runs.md、evidence-pack.md