🐷大肚肚
CF-31C普及+/提高

日程安排

2.0s💾 256MB

📋 题目描述

新学期开始,Berland国立大学的课程表有所变动。根据新的课程表,有 nn 个小组在31号教室上课。对于每个小组,课程的开始时间和结束时间是已知的。然而,无法同时进行所有课程,因为一些小组的上课时间会重叠。只有在某个时刻,一个小组刚结束上课,另一个小组才开始上课,这样它们的上课时间才不会重叠。

系主任希望取消其中一个小组的课程,以确保剩下的小组的上课时间不会相互重叠。你需要找到实现这一目标的所有方法。

📥 输入格式

第一行包含整数 nn1n50001 \leq n \leq 5000)—在31号教室上课的小组数量。接下来 nn 行,每行包含两个整数 lil_irir_i1li<ri1061 \leq l_i < r_i \leq 10^6)—第 ii 组课程的开始和结束时间。初始时可能没有两个课程交叉(参见示例1)。

📤 输出格式

输出整数 kk — 取消课程的方式数量,确保剩余小组的课程时间不相交。第二行输出 kk 个数字,表示可以取消课程的小组索引。小组编号从输入中的给定顺序开始,以递增顺序输出这些数字。

📝 样例 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

💡 题目讲解

1

理解题意

31 号教室有 nn 个小组要上课。每个小组有一个时间段 [l,r][l, r]ll 是开始时间,rr 是结束时间)。

⚠️ 重叠规则:两个组的时间段不能有重叠

  • 如果组 a 在 rar_a 结束,组 b 刚好在 lb=ral_b = r_a 开始 → ✅ 不冲突!端点刚好接上是可以的
  • 但如果 lb<ral_b < r_a(b 在 a 结束前就开始了)→ ❌ 冲突!同一时间两个组都在用教室

🎯 系主任可以取消恰好一个组的课。请你找出:有哪些组,只要取消它,剩下的所有组就互不冲突了?

如果已经互不冲突,那所有 nn 个组都可以是答案(因为取消任何一个之后,剩下的还是不冲突)。

✅ 不重叠(端点相接 OK)[1, 3][3, 10]❌ 重叠(有公共时间)[1, 5][3, 7]重叠区 :(开始 = 结束(端点相接)→ 不重叠开始 < 结束(区间交叉)→ 重叠
1 / 5