Problem:


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



Sample input:
3 2
1 7 2
7 8 1
8 12 1


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
N_C = list(map(int, input().split()))
s_t_c = []
for i in range(N_C[0]):
    s_t_c.append(list(map(int, input().split())))

number_list = []
for j in range(10 ** 5):
    number = 0
    for k in range(N_C[0]):
        if s_t_c[k][0] <= j - 1 and s_t_c[k][1] >= j:
            number = number + 1
        if s_t_c[k][0] <= j and s_t_c[k][1] >= j + 1:
            number = number + 1
        if s_t_c[k][0] <= j - 1 and s_t_c[k][1] >= j + 1:
            number = number - 1
    number_list.append(number)

print(max(number_list))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-        
N, C = list(map(int,input().split()))
channel = [[0 for i in range(2*10**5+7)] for j in range(C)]
arr = [0 for i in range(2*10**5+7)]
for i in range(N):
    s, t, c = list(map(int,input().split()))
    channel[c-1][2*s-1] = 1
    channel[c-1][2*t] = -1
for i in range(2*10**5+6):
    for j in range(C):
        if(channel[j][i]==1 and channel[j][i+1]==-1):
            channel[j][i] = 0
            channel[j][i+1] = 0

ans = 0
use = 0
for i in range(2*10**5+7):
    for j in range(C):
        use += channel[j][i]
        ans = max(ans,use)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-        
import numpy as np

N, C = list(map(int,input().split()))
channel = np.zeros((C,2*10**5+7),dtype='int')
arr = [0 for i in range(2*10**5+7)]
for i in range(N):
    s, t, c = list(map(int,input().split()))
    channel[c-1][2*s-1] = 1
    channel[c-1][2*t] = -1
for i in range(2*10**5+6):
    for j in range(C):
        if(channel[j][i]==1 and channel[j][i+1]==-1):
            channel[j][i] = 0
            channel[j][i+1] = 0

ans = 0
use = 0
for i in range(2*10**5+7):
    for j in range(C):
        use += channel[j][i]
        ans = max(ans,use)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import itertools as it

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


N, C = LI()
s, t, c = [], [], []
for _ in range(N):
    s_, t_, c_ = LI()
    s.append(s_*2 - 1)
    t.append(t_*2)
    c.append(c_)

left = min(s)
right = max(t)
length = right - left + 1

tape = np.zeros(length)

for i in range(N):
    row = np.array([0]*(s[i]-left) + [1]*(t[i]-s[i]+1) + [0]*(right-t[i]))
    tape += np.array(row)

print(int(max(tape)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, C = map(int, input().split(' '))
s = []
t = []
c = []
for i in range(N):
    s_i, t_i, c_i = map(int, input().split(' '))
    s.append(s_i)
    t.append(t_i)
    c.append(c_i)
T = max(t)
table = np.zeros(2*T)
for i in range(N):
    schedule = np.zeros(2*T)
    schedule[2*s[i]-1: 2*t[i]] = 1
    table += schedule
print(int(np.max(table)))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

nc = raw_input()
nc = nc.split()
n,c = map(int,nc)

tt = np.zeros([(10**5),c],int)

for i in range(n):
    stc = raw_input()
    stc = stc.split()
    s,t,c = map(int,stc)
    j = s
    while j <= t:
        tt[j-1][c-1] = 1
        j += 1

ans = 1
for i in range(10**5):
    ans = max(ans,sum(tt[i]))

print ans

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, input().split())
TVs = [[] for i in range(C)]
for i in range(N):
    s, t, c = map(int, input().split())
    TVs[c - 1].append((s, t))

periods = [0] * (2 * 10 ** 5)

for c, TVc in enumerate(TVs):
    ps = [0] * (2 * 10 ** 5)

    for s, t in TVc:
        ps[s * 2 - 1: t * 2 - 2 + 1] = list(map(lambda x: x + 1, ps[s * 2 - 1: t * 2 - 2 + 1]))

    for i in range(len(ps) - 1):
        ps[i] = max(ps[i], ps[i + 1])

    periods = list(map(sum, zip(periods, ps)))

print(max(periods))

Submission status: Time Limit Exceeded

Solution code:
n, c_no = list(map(int, input().split()))
s, t = [], []
c = []
for i in range(c_no):
    c.append([])
for i in range(n):
    stc = list(map(int, input().split()))
    c[stc[2] - 1].append([stc[0], stc[1]])
a = 10**5*[0]
for i in range(len(c)):
    tmp = 10**5*[0]
    c[i].sort()
    for j in range(len(c[i])):
        for k in range(c[i][j][1] - c[i][j][0] + 1):
            if(tmp[c[i][j][0] + k - 1] == 0):
                tmp[c[i][j][0] + k - 1] += 1
    for j in range(10**5):
        a[j] += tmp[j]
print(max(a))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

n, c = list(map(int, sys.stdin.readline().strip().split(" ")))

start_list = []
end_list = []
c_list = []
min_time = 10**5
max_time = 0
for _ in range(n):
    s, t, c = list(map(int, sys.stdin.readline().strip().split(" ")))
    start_list.append(s)
    end_list.append(t)
    c_list.append(c)
    max_time = max(t, max_time)
    min_time = min(s, min_time)

start_list = np.array(start_list)
end_list = np.array(end_list)
c_list = np.array(c_list)

index_list = np.argsort(start_list)
start_list = start_list[index_list]
end_list = end_list[index_list]
c_list = c_list[index_list]

current_channel = []
current_tv = []
top = 0
res = 0

for i in range((max_time - min_time + 1) * 2):
    t = 0.5 * i + (min_time - 0.5)
    while(top < n) and (start_list[top] - 0.5 == t):
        if c_list[top] not in current_channel:
            current_tv.append(top)
        top+=1
    tmp = list(current_tv)
    current_channel = []
    for index in tmp:
        if (end_list[index] == t):
            current_tv.remove(index)
        else:
            if c_list[index] not in current_channel:
                current_channel.append(c_list[index])
    res = max(res, len(current_channel))
            
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

n, c = list(map(int, sys.stdin.readline().strip().split(" ")))

start_list = []
end_list = []
c_list = []
max_time = 0
for _ in range(n):
    s, t, c = list(map(int, sys.stdin.readline().strip().split(" ")))
    start_list.append(s)
    end_list.append(t)
    c_list.append(c)
    max_time = max(t, max_time)

start_list = np.array(start_list)
end_list = np.array(end_list)
c_list = np.array(c_list)

index_list = np.argsort(start_list)
start_list = start_list[index_list]
end_list = end_list[index_list]
c_list = c_list[index_list]

current_channel = []
current_tv = []
top = 0
res = 0

for i in range(max_time * 2):
    t = 0.5 * (i+1)
    while(top < n) and (start_list[top] - 0.5 == t):
        if c_list[top] not in current_channel:
            current_tv.append(top)
        top+=1
    tmp = list(current_tv)
    current_channel = []
    for index in tmp:
        if (end_list[index] == t):
            current_tv.remove(index)
        else:
            if c_list[index] not in current_channel:
                current_channel.append(c_list[index])
    res = max(res, len(current_channel))
            
print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-        
import numpy as np

N, C = list(map(int,input().split()))
channel = np.zeros((C,2*10**5+7),dtype='bool')
for i in range(N):
    s, t, c = list(map(int,input().split()))
    channel[c-1][2*s-1:2*t] = True

ans = 0
for i in range(2*10**5+7):
    ans = max(np.sum(channel[:,i]),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

N,C=map(int,input().split())
channel=[tuple(map(int,input().split())) for i in range(N)]
channel=sorted(channel,key=lambda cha: cha[0])

n=0
while(channel!=[]):
    c=copy.copy(channel)
    n+=1
    pro=channel[0]
    c.remove(pro)
    for i in channel:
        if i[0]>pro[1]:
            pro=i
            c.remove(pro)
    channel=c
print(n)

Submission status: Memory Limit Exceeded

Solution code:
A,B=list(map(int,input().split()))
l=[set([]) for i in range(100001)]
for i in range(A):
   X,Y,Z=list(map(int,input().split()))
   for j in range(X-1,Y):
      l[j].add(Z)
ans=0
for i in l:
   ans=max(ans,len(i))
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
from operator import attrgetter


class Data:
    def __init__(self, s, t, c):
        self.s = s
        self.t = t
        self.c = c


N, C = map(int, input().split())
data_list = []
for _ in range(N):
    s, t, c = map(int, input().split())
    data_list.append(Data(s, t, c))

ch_map = {}
for data in data_list:
    if data.c in ch_map:
        ch_map[data.c].append(data)
    else:
        ch_map[data.c] = [data]
data_list = []

for key, val in ch_map.items():
    ch_list = sorted(val, key=attrgetter("s"))
    m = {}
    end = 0
    for ch in ch_list:
        if end <= ch.s:
            for i in range(ch.s-1, ch.t):
                m[i] = 1
            end = ch.t
        elif end > ch.t:
            for i in range((end+1, ch.t)):
                m[i] = 1
            end = ch.t
    ch_map[key] = m

max = 0
# print(ch_map)
for i in range(100001):
    cnt = 0
    for key, val in ch_map.items():
        if i in val:
            cnt += 1
    if cnt > max:
        max = cnt
    cnt = 0
print(max)

Submission status: Memory Limit Exceeded

Solution code:
from operator import attrgetter


class Data:
    def __init__(self, s, t, c):
        self.s = s
        self.t = t
        self.c = c


N, C = map(int, input().split())
data_list = []
for _ in range(N):
    s, t, c = map(int, input().split())
    data_list.append(Data(s, t, c))

ch_map = {}
for data in data_list:
    if data.c in ch_map:
        ch_map[data.c].append(data)
    else:
        ch_map[data.c] = [data]

for key, val in ch_map.items():
    ch_list = sorted(val, key=attrgetter("s"))
    m = {}
    end = 0
    for ch in ch_list:
        if end <= ch.s:
            for i in range(ch.s-1, ch.t):
                m[i] = 1
            end = ch.t
        elif end > ch.t:
            for i in range((end+1, ch.t)):
                m[i] = 1
            end = ch.t
    ch_map[key] = m

max = 0
# print(ch_map)
for i in range(100001):
    cnt = 0
    for key, val in ch_map.items():
        if i in val:
            cnt += 1
    if cnt > max:
        max = cnt
    cnt = 0
print(max)

Submission status: Memory Limit Exceeded

Solution code:


def foo(n, c, targets):
    timeline = {}
    for s, t, c in targets:
        for i in range(s-1, t):
            xs = timeline.get(i, None)
            if xs is None:
                xs = set()
            xs.add(c)
            timeline[i] = xs
    return max([len(v) for k, v in timeline.items()])




if __name__ == "__main__":
    n,c  = map(int, input().split())

    targets = []
    for i in range(n):
        s, t, c = list(map(int, input().split()))
        targets.append((s,t,c))
        
    print(foo(n, c, targets))

Submission status: Accepted

Solution code:
def Recording():
    n, c = map(int, input().split())
    num = 2*10**5+1 

    # チャンネルごとにimos配列
    imos = [[0]*num for _ in range(c)]
    
    # imos
    for _ in range(n):
        s, t, c0 = map(int, input().split())
        if imos[c0-1][s*2] < 0 and imos[c0-1][t*2-1] > 0:
            imos[c0-1][s*2] = 0
            imos[c0-1][t*2-1] = 0
        elif imos[c0-1][s*2] < 0:            
            imos[c0-1][s*2] = 0
            imos[c0-1][t*2] -= 1
        elif imos[c0-1][t*2-1] > 0:    
            imos[c0-1][s*2-1] += 1
            imos[c0-1][t*2-1] = 0
        else:
            imos[c0-1][s*2-1] += 1
            imos[c0-1][t*2] -= 1
    ans = [0 for _ in range(num)]
    for i in range(c):
        for j in range(1, num):
            imos[i][j] += imos[i][j-1]
            ans[j] += imos[i][j]
    print(max(ans))
    
if __name__ == '__main__':
    Recording()

Submission status: Accepted

Solution code:
from collections import deque
N, C = map(int, input().split())
que = []
Que = []
channel = [[] for i in range(C+1)]
for i in range(N):
    s, t, c = map(int, input().split())
    channel[c].append((s, t))
for i in range(C+1):
    channel[i].sort()
    tmp_que = deque(channel[i])
    left_que = deque([])
    if tmp_que:
        x, y = tmp_que.popleft()
        left_que.append((x, y))
        while tmp_que:
            lx, ly = left_que.pop()
            rx, ry = tmp_que.popleft()
            if ly == rx:
                left_que.append((lx, ry))
            elif ly < rx:
                left_que.append((lx, ly))
                left_que.append((rx, ry))
    for x, y in left_que:
        Que.append((2*x-1, 1))
        Que.append((2*y, -1))
ans = 0
value = 0
Que.sort(reverse=True)
while Que:
    v, command = Que.pop()
    value += command
    ans = max(ans, value)
print(ans)

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
K = [[0]*(10**5+1) for _ in range(C+1)]
T = [[] for _ in range(C+1)]
for i in range(N):
    s, t, c = map(int, input().split())
    T[c].append([s, t])
    K[c][t] = 1

for i in range(C+1):
    for j in range(len(T[i])):
        s, t = T[i][j]
        if K[i][s] == 0:
            T[i][j][0] -= 0.5
P = [0]*(10**6)
for i in range(C+1):
    for j in range(len(T[i])):
        for k in range(int(2*T[i][j][0]), 2*T[i][j][1]):
            P[k] += 1
print(max(P))

Submission status: Accepted

Solution code:
from sys import stdin

def getval():
    n,c = map(int,stdin.readline().split())
    s = [list(map(int,stdin.readline().split())) for i in range(n)]
    return n,c,s

def main(n,c,s):
    arr = [[0 for i in range(c)] for i in range(10**5)]
    for i in s:
        ch = i[2]-1
        for j in range(i[0]-1,i[1]):
            arr[j][ch] = 1
    ans = 0
    for i in range(10**5):
        loc = arr[i]
        temp = 0
        for j in range(c):
            temp += loc[j]
        ans = max(temp,ans)
    print(ans)

if __name__=="__main__":
    n,c,s = getval()
    main(n,c,s)

Submission status: Accepted

Solution code:
from itertools import accumulate


def main():
    n, c = map(int, input().split())
    p = [[] for _ in range(c + 1)]
    for _ in range(n):
        *st, cc = map(int, input().split())
        p[cc].append(st)
    all_p = [0] * (10 ** 5 + 10)
    for pp in p:
        if len(pp) == 0:
            continue
        pp.sort()
        last_start, last_end = pp[0]
        for start, end in pp[1:]:
            if start == last_end:
                last_end = end
            else:
                all_p[last_start - 1] += 1
                all_p[last_end] -= 1
                last_start, last_end = start, end
        all_p[last_start - 1] += 1
        all_p[last_end] -= 1
    print(max(accumulate(all_p)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


def main():
    n, c = map(int, input().split())
    program = [[] for _ in range(c)]
    for _ in range(n):
        s, t, cc = map(int, input().split())
        cc -= 1
        s *= 2
        t *= 2
        program[cc].append([s - 1, t])
    all_p = []
    for i in range(c):
        if len(program[i]) == 0:
            continue
        now = program[i]
        now.sort(key=lambda x: x[1])
        last_begin, last_end = now[0]
        for begin, end in now[1:]:
            if begin + 1 == last_end:
                last_end = end
            else:
                all_p.append([last_begin, last_end, i])
                last_begin = begin
                last_end = end
        all_p.append([last_begin, last_end, i])
    all_p.sort()
    q = [(-1, -1)]
    for begin, end, now_channel in all_p:
        last_end, last_channel = q[0]
        if last_end < begin or now_channel == last_channel:
            heappop(q)
        heappush(q, (end, now_channel))
    print(len(q))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, C = na()
ans = [0] * ((10 ** 5) * 2 + 10)
for i in range(N):
    s, t, c = na()
    ans[s] += 1
    ans[t+1] -= 1

for i in range(len(ans)-1):
    ans[i+1] += ans[i]
print(min(max(ans), C))

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
cusum = [[0 for j in range(10**5+1)] for i in range(C+1)]
for i in range(N):
    s, t, c = map(int, input().split())
    cusum[c][s] += 1
    cusum[c][t] += -1
ans = 0
s = 0
for j in range(10**5+1):
    cp = 0
    cm = 0
    for i in range(C+1):
        if cusum[i][j] == 1:
            cp += 1
        elif cusum[i][j] == -1:
            cm += 1
    s += cp
    ans = max(s, ans)
    s -= cm

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def main():
    with open(0) as f:
        N, C = map(int, f.readline().split())
        Rec = [tuple(map(int, f.readline().split())) for _ in range(N)]
    
    time_line_by_channel = np.array([[0] * (10**5+1) for _ in range(C+1)])
    #チャンネルごとにタイムラインを作成
    for s, t, c in Rec:
        time_line_by_channel[c, s-1:t] = 1
    #タイムライン結合
    joined_timeline = np.sum(time_line_by_channel, axis=0)
    ans = max(joined_timeline)
    print(ans)

main()

Submission status: Accepted

Solution code:
import itertools

n,c=map(int,input().split())
dp=[[0]*100002 for i in range(c)]

for i in range(n):
    s,t,x=map(int,input().split())
    dp[x-1][s-1]+=1
    dp[x-1][t]-=1

for i in range(c):
    dp[i]=list(itertools.accumulate(dp[i]))


ans=0

for i in range(100001):
    cnt=0
    for j in range(c):
        if dp[j][i]!=0:
            cnt+=1
    
    ans=max(ans,cnt)


print(ans)

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
ch = [[0]*(10**5+1) for _ in range(C)]

for _ in range(N):
  s, t, c = map(int, input().split())
  ch[c-1][s] += 1
  ch[c-1][t] -= 1

for c in range(C):
  for i in range(10**5):
    if ch[c][i+1] == 1:
      ch[c][i+1] = ch[c][i+1] + ch[c][i]
      ch[c][i] = 1
    else:
      ch[c][i+1] = ch[c][i+1] + ch[c][i]

ans = 0
for i in range(10**5):
  temp = 0
  for c in range(C):
    temp += ch[c][i+1]
  ans = max(ans, temp)

print(ans)

Submission status: Accepted

Solution code:
n, C = map(int, input().split())
stc = [list(map(int, input().split())) for i in range(n)]
m = 0
for i in stc:
    m = max(m, i[1])
lis = [[0] * C for i in range(m + 1)]
for i in stc:
    for j in range(i[0], i[1] + 1):
        lis[j][i[2] - 1] = 1
ans = 0
for i in lis:
    ans = max(ans, sum(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq

input = sys.stdin.readline
N, C = map(int, input().split())
stc = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
tmp = [[] for _ in range(C)]
for s, t, c in stc:
    if len(tmp[c - 1]) != 0 and tmp[c - 1][-1][1] == s:
        tmp[c - 1][-1][1] = t
    else:
        tmp[c - 1].append([s, t, c])
stc_clean = []
for e in tmp:
    stc_clean += e
stc_clean = sorted(stc_clean, key=lambda x: x[0])

hq = []
heapq.heapify(hq)

ans = 0
for s, t, _ in stc_clean:
    while len(hq) > 0 and hq[0][0] < s:
        heapq.heappop(hq)
    heapq.heappush(hq, (t, s, c))
    ans = max(ans, len(hq))
print(ans)

Submission status: Accepted

Solution code:
T = 10**5+1
N, C = map(int, input().split())
h = [[] for _ in range(C)]
for i in range(N):
    s, t, c = map(int, input().split())
    s -= 1
    t -= 1
    c -= 1
    h[c].append([s, t])

v = [0]*T
for i in range(C):
    if len(h[i]) == 0:
        continue
    h[i].sort()
    c = h[i]
    if len(c) > 0:
        f = []
        f.append(c[0])
        for j in range(1, len(c)):
            if f[-1][1] != c[j][0]:
                f.append(c[j])
            else:
                f[-1] = [f[-1][0], c[j][1]]
        for s, t in f:
            v[s] += 1
            v[t+1] -= 1

ans = 0
use = 0
for i in range(T):
    use += v[i]
    ans = max(ans, use)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import copy
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def solve():
    n,C = getList()
    li = []

    start = [[0] * 100100 for i in range(31)]
    end = [[0] * 100100 for i in range(31)]
    pt = [0] * 100100

    for i in range(n):
        s, t, c = getList()
        start[c][s] += 1
        end[c][t] += 1
        pt[s] += 1
        pt[t+1] -= 1

    for i in range(100099):
        pt[i+1] += pt[i]

    ans = 0
    for i in range(100100):
        tmp = pt[i]
        for j in range(31):
            if start[j][i] and end[j][i]:
                tmp -= 1
        ans = max(ans, tmp)

    print(ans)






def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    n, c = map(int, input().split())
    channels = [[] for _ in range(c)]
    for _ in range(n):
        i, j, k = map(int, input().split())
        channels[k-1].append([i, j])

    programs = []
    for channel in channels:
        if channel == []:
            continue

        channel.sort()
        for i in range(len(channel)-1):
            if channel[i][1] == channel[i+1][0]:
                channel[i+1][0] = channel[i][0]
            else:
                programs.append(channel[i])
        programs.append(channel[-1])

    programs.sort()

    from heapq import heappushpop, heappush

    heap = [programs[0][1]]
    for i in range(1, len(programs)):
        if heap[0] < programs[i][0]:
            heappushpop(heap, programs[i][1])
        else:
            heappush(heap, programs[i][1])
    
    print(len(heap))

main()

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    n, c = map(int, input().split())
    channels = [[] for _ in range(c)]
    for _ in range(n):
        i, j, k = map(int, input().split())
        channels[k-1].append([i, j])

    programs = []
    for channel in channels:
        if channel == []:
            continue

        channel.sort()
        for i in range(len(channel)-1):
            if channel[i][1] == channel[i+1][0]:
                channel[i+1][0] = channel[i][0]
            else:
                programs.append(channel[i])
        programs.append(channel[-1])

    programs.sort()

    from heapq import heapify, heappushpop, heappush

    heap = [programs[0][1]]
    heapify(heap)
    for i in range(1, len(programs)):
        if heap[0] < programs[i][0]:
            heappushpop(heap, programs[i][1])
        else:
            heappush(heap, programs[i][1])
    
    print(len(heap))

main()

Submission status: Accepted

Solution code:
import itertools
N,C=map(int,input().split())
ch =[[] for _ in range(C+1)]
time= [0]*(10**5+1)
for _ in range(N):
    s,t,c=map(int,input().split())
    ch[c].append(s)
    ch[c].append(t)
    
for i in range(1,C+1):
    ch[i].sort()

for i in range(1,C+1):
    for chi in range(len(ch[i])):
        if chi %2 == 0:
            if chi == 0:
                time[ch[i][chi]-1]+=1
            elif chi>1 and ch[i][chi-1]!=ch[i][chi]:
                time[ch[i][chi]-1]+=1
        elif chi %2 == 1:
            if chi==len(ch[i])-1:
                time[ch[i][chi]]-=1
            elif ch[i][chi+1] != ch[i][chi]:
                time[ch[i][chi]]-=1

integ_time = itertools.accumulate(time)
print(max(integ_time))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import accumulate
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,c = map(int,readline().split())
stc = []
for i in range(n):
    stc.append(list(map(int,readline().split())))
stc.sort(key=lambda x: (x[2], x[0]))
 
nstc = []
for i in range(n):
    if len(nstc) > 0 and nstc[-1][2] == stc[i][2] and nstc[-1][1] == stc[i][0]: #同じチャンネルかつ終了時刻と始まりの時刻が同じ
        nstc[-1][1] = stc[i][1]
    else:
        nstc.append(stc[i])
n = len(nstc)
 
h = [0]*200005
for i in range(n):
    h[2*nstc[i][0] - 1] += 1
    h[2*nstc[i][1]] += -1
ah = list(accumulate(h))
print(max(ah))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop,heappush
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,C = map(int,readline().split())
data = [[] for _ in range(C+1)]
for i in range(N):
    s,t,c = map(int,readline().split())
    data[c].append((s,t))

TV = []
for d in data:
    N = len(d)
    if N == 0:
        continue
    d = sorted(d)
    g = d[0][1]
    cnt = 0
    for i in range(N-1):
        if g == d[i+1][0]:
            cnt += 1
        else:
            TV.append((d[i-cnt][0],d[i][1]))
            cnt = 0
        g = d[i+1][1]
    TV.append((d[-(1+cnt)][0],d[-1][1]))

TV = sorted(TV)
len_TV = len(TV)
q = [TV[0][1]]

for i in range(1,len_TV):
    s = TV[i][0]
    g = TV[i][1]
    m = heappop(q)
    if m >= s:
        heappush(q,m)
    heappush(q,g)

print(len(q))

Submission status: Accepted

Solution code:
from numpy import *
N,C = map(int,input().split())
A = zeros((C,10**5),int32)

for n in range(N):
  s,t,c = map(int,input().split())
  A[c-1,s-1:t] = 1
print(max(sum(A,axis=0)))

Submission status: Accepted

Solution code:
from collections import defaultdict

N, C = map(int, input().split())

D = defaultdict(list)
for _ in range(N):
    s, t, c = map(int, input().split())
    D[c-1].append((s, t))

IMOS = [0]*(10**5+2)
for c in range(C):
    D[c].sort(key=lambda x: x[0])

    pt = -1
    for i, (s, t) in enumerate(D[c]):
        if s == pt:
            IMOS[s+1] += 1
            IMOS[t] -= 1
        else:
            IMOS[s-1] += 1
            IMOS[t] -= 1
        pt = t

ans = 0
a = 0
for i in IMOS:
    a += i
    ans = max(ans, a)

print(ans)

Submission status: Accepted

Solution code:
n, C = map(int, input().split())
time = 0
stc = []
for i in range(n):
    temp = list(map(int, input().split()))
    time = max(time, temp[1])
    stc.append(temp)
tv = [[0 for i in range(C)] for i in range(time + 1)]
for i in stc:
    s, t, c = i[0], i[1], i[2]
    for j in range(s, t + 1):
        tv[j][c - 1] = 1
ans = 0
for i in tv:
    ans = max(ans, sum(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,c=map(int,input().split())
prog=[]
stc=[]
for i in range(n):
    x=tuple(map(int,input().split()))
    stc.append(x)
stc=sorted(stc)
video=[[0]*(10**5+1) for i in range(30)]
for s,t,ci in stc:
    if video[ci-1][s]!=-1:
        video[ci-1][s-1]+=1
        video[ci-1][t]-=1
    else:
        video[ci-1][s]=0
        video[ci-1][t]-=1
newvideo=[]
for i in range(10**5+1):
    cnt=0
    for c in range(30):
        cnt+=video[c][i]
    newvideo.append(cnt)

from itertools import accumulate
videoacc=list(accumulate(newvideo))

print(max(videoacc))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,C = list(map(int, input().split()))
stc = [tuple(map(int, input().split())) for _ in range(n)]
T = max(item[1] for item in stc)
l = [[False]*(T+1) for _ in range(C)]
for s,t,c in stc:
    for i in range(s-1,t):
        l[c-1][i] = True
ans = max(sum(l[c][i] for c in range(C)) for i in range(T+1))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, C = (int(x) for x in input().split())
R = [[0]*100000 for _ in range(C)] #R[c][t]:時刻t+1にチャンネルc+1を録画するのに必要な録画機の個数
R = np.array(R)
for _ in range(N):
    s, t, c = map(int,input().split())
    R[c-1,s-1:t] = 1
ans = max(sum(R))
print(ans)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  N,C=LI()
  l=[[0]*100100 for _ in range(C)]

  for _ in range(N):
    s,t,c=LI()
    l[c-1][s]+=1
    l[c-1][t+1]-=1

  for i in range(C):
    for j in range(100000):
      l[i][j+1]+=l[i][j]

  for i in range(C):
    for j in range(100000):
      if l[i][j]==2:
        l[i][j]=1

  mx=0
  for i in range(100000):
    sm=0
    for j in range(C):
      sm+=l[j][i]
    mx=max(mx,sm)

  return mx

# main()
print(main())

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
TV=[[0]*C for i in range(10**5)]
for i in range(N):
  s,t,c=map(int,input().split())
  for i in range(s-1,t):
    TV[i][c-1]=1
print(max([sum(TV[i]) for i in range(10**5)]))