民族展演排期：单舞台节目场次最大化 完整解题档案

档案概况

题目、题干与输入输出

正式题面

源文件：official-prompt.md

规则来源

• 赛项说明页码：15
• 训练题主题：民族展演排期：单舞台节目场次最大化
• 所属赛道：民族文化赛道

题目背景

民族展演只有一块主舞台，但节目候选很多。为了在不冲突的前提下安排尽可能多的节目，需要按固定选择规则做贪心排期，并输出最终上台顺序。

任务描述

• 读取所有节目时间区间。
• 按结束时间优先的固定规则选择最多个互不冲突的节目。
• 输出最终安排的节目数和节目名称序列。

输入格式

1. 第一行输入一个整数 n，表示候选节目数。
2. 接下来 n 行，每行输入 name start end。

输出格式

1. 第一行输出 selected=最大可安排节目数。
2. 第二行输出 shows=按最终安排顺序输出节目名，英文逗号分隔；若为空输出 shows=NONE。

数据范围与说明

• 1 <= n <= 200000。
• 0 <= start < end <= 10^9。
• 时间区间按 [start, end) 处理，前一场 end == 后一场 start 视为不冲突。
• 选择规则固定为按 end 升序、start 升序、输入顺序升序排序后做贪心。

样例输入

5
A 1 4
B 3 5
C 0 6
D 5 7
E 8 9

样例输出

selected=3
shows=A,D,E

样例解释

• 按规则排序后可依次选择 A、D、E。
• B 和 C 都会与已选节目冲突，因此被跳过。
• 最终最多可安排 3 场节目。

知识点清单

• 区间冲突判定与半开区间 [start, end)。
• 多关键字排序。
• 结束时间最早优先的贪心策略。
• 贪心选择过程的顺序模拟。
• 结果序列的稳定输出。

约束拆解

源文件：parsed-constraints.md

显式约束

• 1 <= n <= 200000。
• 0 <= start < end <= 10^9。
• 时间区间按 [start, end) 处理，前一场 end == 后一场 start 视为不冲突。
• 选择规则固定为按 end 升序、start 升序、输入顺序升序排序后做贪心。

建模拆解

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

易错边界

• 多个节目结束时间相同，必须继续按开始时间和输入顺序比较。
• 只有一场节目或所有节目完全重叠时，也要输出正确结果。
• 当没有节目被选中时，第二行必须输出 shows=NONE。

计分模型

源文件：scoring-model.md

判题方式

• 主判题方式：optimization
• 主算法：按结束时间排序的区间贪心

判题重点

• 重点校验建模是否正确、最优值维护是否稳定、路径或方案恢复是否完整。
• 隐藏数据会覆盖不可达、同值竞争和多约束并存情形。

公开样例建议

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

隐藏数据建议

• 准备完全不冲突、完全重叠和首尾相接三类区间。
• 准备结束时间相同的节目，验证多关键字排序规则。
• 准备节目数很大但多数都可兼容的样例，检查性能。

验收清单

源文件：acceptance-checklist.md

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

样例输入输出

样例输入：sample.in

5
A 1 4
B 3 5
C 0 6
D 5 7
E 8 9

样例输出：sample.out

selected=3
shows=A,D,E

题解、建模与最终解法

自动整理的解题流程

• 题目主题：民族展演排期：单舞台节目场次最大化
• 题目摘要：按结束时间排序做区间贪心，求出单舞台可安排的最大节目场次。
• 判题提示：该题以优化求解为主，重点是约束建模、可行性检查和最优值维护。
• 先完成输入、对象、约束和输出的四步建模，再落到具体算法和实现。
• 优先用样例验证最小流程，再补边界测试和错误分支。

解题思路

源文件：solution-rationale.md

1. 问题重述

按结束时间排序做区间贪心，求出单舞台可安排的最大节目场次。

2. 数据结构与建模

• 主算法：按结束时间排序的区间贪心
• 输入拆解后对应的数据结构要和输出项一一对应。
• 需要重点维护的状态包括：题目实体、核心指标、中间结果和最终答案。

3. 算法步骤

1. 把所有节目按结束时间、开始时间和输入顺序排序。
2. 从前到后扫描，若当前节目开始时间不早于上一场结束时间，就选入答案。
3. 每次选入后更新当前已占用到的结束时间。
4. 扫描结束后输出场次数和节目名称列表。

4. 正确性说明

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

5. 复杂度分析

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

6. 易错点

• 多个节目结束时间相同，必须继续按开始时间和输入顺序比较。
• 只有一场节目或所有节目完全重叠时，也要输出正确结果。
• 当没有节目被选中时，第二行必须输出 shows=NONE。

7. 知识点清单

• 区间冲突判定与半开区间 [start, end)。
• 多关键字排序。
• 结束时间最早优先的贪心策略。
• 贪心选择过程的顺序模拟。
• 结果序列的稳定输出。

设计决策记录

源文件：decision-log.md

• 选择 按结束时间排序的区间贪心 作为主算法，因为它能直接覆盖题目的核心约束。
• 单机位最大兼容区间数是标准区间调度问题。
• 把排序规则写进比较键，能保证程序输出与题意一致。
• Python 与 C++ 版本统一输出格式，便于双语训练和证据采集。

验证计划

源文件：validation-plan.md

• 先验证题面公开样例，确保基础流程无误。
• 准备完全不冲突、完全重叠和首尾相接三类区间。
• 准备结束时间相同的节目，验证多关键字排序规则。
• 准备节目数很大但多数都可兼容的样例，检查性能。
• 最后再补 1 组手工构造的极小数据，确认程序不会依赖特殊输入规模。

备选方案

源文件：alternatives.md

最终代码与实现

Python 主实现

源文件：main.py

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

import sys


def solve(data: str) -> str:
    tokens = data.split()
    if not tokens:
        return ""
    it = iter(tokens)
    n = int(next(it))
    shows = []
    for order in range(n):
        name = next(it)
        start = int(next(it))
        end = int(next(it))
        shows.append((end, start, order, name))
    shows.sort()
    selected = []
    last_end = -1
    for end, start, _, name in shows:
        if start >= last_end:
            selected.append(name)
            last_end = end
    line = ",".join(selected) if selected else "NONE"
    return f"selected={len(selected)}\nshows={line}"


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

C++ 对照实现

源文件：main.cpp

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

#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) {
        return 0;
    }
    vector<tuple<int, int, int, string>> shows;
    for (int order = 0; order < n; ++order) {
        string name;
        int start, end;
        cin >> name >> start >> end;
        shows.push_back({end, start, order, name});
    }
    sort(shows.begin(), shows.end());
    vector<string> selected;
    int last_end = -1;
    for (const auto& show : shows) {
        int end = get<0>(show);
        int start = get<1>(show);
        const string& name = get<3>(show);
        if (start >= last_end) {
            selected.push_back(name);
            last_end = end;
        }
    }
    cout << "selected=" << selected.size() << "\n";
    cout << "shows=";
    if (selected.empty()) {
        cout << "NONE";
    } else {
        for (size_t i = 0; i < selected.size(); ++i) {
            if (i) {
                cout << ',';
            }
            cout << selected[i];
        }
    }
    cout << "\n";
    return 0;
}

代码执行与运行结果

最新成功运行

PY 运行输出摘录

selected=3
shows=A,D,E

CPP 运行输出摘录

selected=3
shows=A,D,E

全部运行记录索引

调试、修正与流程留痕

调试日志

源文件：debug-journal.md

失败案例目录

源文件：failure-catalog.md

编码过程记录

源文件：implementation-journal.md

全流程文件导航

• 题目总览：s4-jh-05-stage-schedule/README.md
• 题面与约束：official-prompt.md、parsed-constraints.md、scoring-model.md、acceptance-checklist.md
• 代码与样例：10-cases/s4-jh-05-stage-schedule/02-solution
• 运行证据：10-cases/s4-jh-05-stage-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