分数: 400 点
问题陈述
Joisino 正在计划录制 N 带有录音机的电视节目。
电视可以接收 C 频道编号 1 通过 C.
的 i她要录制的节目从时间开始播出 s_i 到时间 t_i (包括时间 s_i 但不是 频道上的 t_i) c_i.
在这里,同一频道上永远不会同时播放多个节目。
当录音机正在录制某个频道时 S 到时间 T (包括时间 S 但不是 频道上的 T),无法从时间开始录制其他通道 S-0.5 到时间 T (包括时间 S-0.5 但不是 频道上的 T).
求出记录通道所需的最少记录器数量,以便所有通道 N 节目已录制完毕。
约束
- 1≤N≤10^5
- 1≤C≤30
- 1≤s_i<t_i≤10^5
- 1≤c_i≤C
- If c_i=c_j 和 i≠j,或者 t_i≤s_j or s_i≥t_j.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N C s_1 t_1 c_1 : s_N t_N c_N
输出
当所需的最小记录器数量为 x,打印值 x.
示例输入 1
3 2 1 7 2 7 8 1 8 12 1
示例输出 1
2
两台录像机可以录制所有节目,例如如下:
- 用第一台录音机,录制频道 2 从时间 1 到时间 7。将录制第一个节目。请注意,此录音机将无法录制其他频道 0.5 到时间 7.
- 用第二个录音机,记录频道 1 从时间 7 到时间 12。第二个和第三个节目将被录制。请注意,此录音机将无法录制其他频道 6.5 到时间 12.
示例输入 2
3 4 1 3 2 3 4 4 1 4 3
示例输出 2
3
可能某个频道没有可录制的节目。
示例输入 3
9 4 56 60 4 33 37 2 89 90 3 32 43 1 67 68 3 49 51 3 31 32 3 70 71 1 11 12 3
示例输出 3
2