正式训练题面

规则来源

• 赛项说明页码：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)。
• 多关键字排序。
• 结束时间最早优先的贪心策略。
• 贪心选择过程的顺序模拟。
• 结果序列的稳定输出。