CF-31C普及+/提高
日程安排
⏱ 2.0s💾 256MB
📋 题目描述
新学期开始,Berland国立大学的课程表有所变动。根据新的课程表,有 个小组在31号教室上课。对于每个小组,课程的开始时间和结束时间是已知的。然而,无法同时进行所有课程,因为一些小组的上课时间会重叠。只有在某个时刻,一个小组刚结束上课,另一个小组才开始上课,这样它们的上课时间才不会重叠。
系主任希望取消其中一个小组的课程,以确保剩下的小组的上课时间不会相互重叠。你需要找到实现这一目标的所有方法。
📥 输入格式
第一行包含整数 ()—在31号教室上课的小组数量。接下来 行,每行包含两个整数 和 ()—第 组课程的开始和结束时间。初始时可能没有两个课程交叉(参见示例1)。
📤 输出格式
输出整数 — 取消课程的方式数量,确保剩余小组的课程时间不相交。第二行输出 个数字,表示可以取消课程的小组索引。小组编号从输入中的给定顺序开始,以递增顺序输出这些数字。
📝 样例 1
输入
3 3 10 20 30 1 3
输出
3 1 2 3
📝 样例 2
输入
4 3 10 20 30 1 3 1 39
输出
1 4
📝 样例 3
输入
3 1 5 2 6 3 7
输出
0
📚 来源
Problem:CF-31C
Contest:Codeforces Beta Round #31 (Div. 2, Codeforces format)
💡 题目讲解
1
理解题意
31 号教室有 个小组要上课。每个小组有一个时间段 ( 是开始时间, 是结束时间)。
⚠️ 重叠规则:两个组的时间段不能有重叠。
- 如果组 a 在 结束,组 b 刚好在 开始 → ✅ 不冲突!端点刚好接上是可以的
- 但如果 (b 在 a 结束前就开始了)→ ❌ 冲突!同一时间两个组都在用教室
🎯 系主任可以取消恰好一个组的课。请你找出:有哪些组,只要取消它,剩下的所有组就互不冲突了?
如果已经互不冲突,那所有 个组都可以是答案(因为取消任何一个之后,剩下的还是不冲突)。
1 / 5