100803: [AtCoder]ABC080 D - Recording

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $400$ points

Problem Statement

Joisino is planning to record $N$ TV programs with recorders.

The TV can receive $C$ channels numbered $1$ through $C$.

The $i$-th program that she wants to record will be broadcast from time $s_i$ to time $t_i$ (including time $s_i$ but not $t_i$) on Channel $c_i$.

Here, there will never be more than one program that are broadcast on the same channel at the same time.

When the recorder is recording a channel from time $S$ to time $T$ (including time $S$ but not $T$), it cannot record other channels from time $S-0.5$ to time $T$ (including time $S-0.5$ but not $T$).

Find the minimum number of recorders required to record the channels so that all the $N$ programs are completely recorded.

Constraints

  • $1≤N≤10^5$
  • $1≤C≤30$
  • $1≤s_i<t_i≤10^5$
  • $1≤c_i≤C$
  • If $c_i=c_j$ and $i≠j$, either $t_i≤s_j$ or $s_i≥t_j$.
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

$N$ $C$
$s_1$ $t_1$ $c_1$
$:$
$s_N$ $t_N$ $c_N$

Output

When the minimum required number of recorders is $x$, print the value of $x$.

Sample Input 1

3 2
1 7 2
7 8 1
8 12 1

Sample Output 1

2

Two recorders can record all the programs, for example, as follows:

  • With the first recorder, record Channel $2$ from time $1$ to time $7$. The first program will be recorded. Note that this recorder will be unable to record other channels from time $0.5$ to time $7$.
  • With the second recorder, record Channel $1$ from time $7$ to time $12$. The second and third programs will be recorded. Note that this recorder will be unable to record other channels from time $6.5$ to time $12$.

Sample Input 2

3 4
1 3 2
3 4 4
1 4 3

Sample Output 2

3

There may be a channel where there is no program to record.

Sample Input 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

Sample Output 3

2

Input

题意翻译

### 题目描述 LBW 打算用摄像机录下 $n$ 个电视节目。 电视可以接收的频道有 $k$ 个。 对于第 $i$ 个电视节目，从时刻 $s_i$ 到时刻 $t_i$，在频道 $c_i$ 被播放；但是**包括时刻 $s_i$，除去时刻 $t_i$**。 为了录下节目，LBW 需要去买摄像机。 摄像机在录制某个频道的时刻 $S$ 到时刻 $T$ 时，从时刻 $(S - 0.5)$ 到时刻 $T$ 之间，不能用于其他频道的录像；但是，**包括时刻 $(S-0.5)$，除去时刻 $T$**。 LBW 想知道，如果将 $n$ 个节目全部录下来，最少需要几个摄像机。 ### 输入格式 第一行两个数 $n$ 与 $k$。 接下来 $n$ 行，每行三个数 $s_i$，$t_i$ 与 $c_i$。 ### 输出格式 一个数，表示所需的最少摄像机数量。 ### 数据范围 $1 \le n \le 10^5$ $1 \le k \le 30$ $1 \le s_i < t_i \le 10^5$ 数据保证： $1 \le c_i \le k$ 如果 $c_i = c_j$ 且 $i \not=j$，则 $t_i \le s_j$ 或者 $s_i \ge t_j$ 中必有一个成立。 所有数据均为整数。

Source/Category

加入题单

算法标签：