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: Accepted

Solution code:
MAX_T = 2 * 10 ** 5


def main():
    n, c = map(int, input().split())

    ch = [[] for i in range(c)]
    for i in range(n):
        si, ti, ci = map(int, input().split())
        ch[ci-1].append([si, ti])

    for i in range(c):
        if len(ch[i]) != 0:
            ch[i].sort(key=lambda lst: lst[0])
            pro_lst = [ch[i][0]]
            for j in range(1, len(ch[i])):
                if ch[i][j][0] == pro_lst[-1][1]:
                    pro_lst[-1][1] = ch[i][j][1]
                else:
                    pro_lst.append(ch[i][j])
            ch[i] = pro_lst

    im = [0 for i in range(MAX_T+1)]
    for i in range(c):
        for j in range(len(ch[i])):
            im[2*ch[i][j][0]-1] += 1
            im[2*ch[i][j][1]] -= 1

    im_s = [0 for i in range(MAX_T+1)]
    for i in range(1, len(im)):
        im_s[i] = im_s[i-1] + im[i]

    print(max(im_s))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, c = map(int, input().split())
T = 10**5+1
l = [[0]*c for _ in range(T)]

for _ in range(n):
    s, t, c_ = map(int, input().split())
    c_ -= 1
    for i in range(s-1, t):
        l[i][c_] = 1

ans = 0
for i in range(T):
    ans = max(ans, sum(l[i]))

print(ans)

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
tv = [list(map(int, input().split())) for _ in range(N)]

max_t = max(tv, key=lambda x: x[1])[1]
channels = [[0 for _ in range(max_t)] for _ in range(C)]

for s, t, c in tv:
    channels[c - 1][s - 1:t] = [1] * (t - s + 1)

ans = 0
for T in list(zip(*channels)):
    ans = max(ans, sum(T))
print(ans)

Submission status: Accepted

Solution code:
n, c = map(int, input().split())
program = [list(map(int, input().split())) for _ in range(n)]

table = [[0 for _ in range(c)] for _ in range(10 ** 5)]

for p in program:
	for i in range(p[0] - 1, p[1]):
		table[i][p[2]-1] = 1

ans = 1

for i in range(10 ** 5):
	s = sum(table[i])
	if ans < s:
		ans = s

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,C=map(int,input().split())
stc=[]
c_st=defaultdict(list)
for i in range(N):
    ss,tt,cc = map(int,input().split())
    stc.append((ss,tt,cc))
    c_st[cc].append((ss,tt))

S=[]
T=[]
for c,lst in c_st.items():
    ss=sorted(lst)
    s,t=ss[0]
    for i in range(1,len(lst)):
        if ss[i][0]==ss[i-1][1]:
            t=ss[i][1]
            continue
        else:
            S.append(s-0.5)
            T.append(t)
            s,t=ss[i]
    S.append(s-0.5)
    T.append(t)
S=sorted(S)
T=sorted(T)
count=0
maxc=0
si,ti=0,0
while si<len(S):
    s=S[si]
    t=T[ti]
    if s<t:
        count+=1
        si+=1
    else:
        count-=1
        ti+=1
    if count>maxc:
        maxc=count
print(maxc)

Submission status: Accepted

Solution code:
N,C =map(int,input().split())
chan=[[] for i in range(C)]
for i in range(N):
    a,b,c=map(int,input().split())
    chan[c-1].append([a,b])
for i in range(C):
    chan[i].sort()
imos=[0]*(10**5+2)
for i in range(C):
    if len(chan[i])==0:
        continue
    imos[chan[i][0][0]]+=1
    imos[chan[i][0][1]+1]-=1
    for k in range(1,len(chan[i])):
        if chan[i][k][0]==chan[i][k-1][1]:
            imos[chan[i][k][0]+1]+=1
            imos[chan[i][k][1]+1]-=1
        else:
            imos[chan[i][k][0]]+=1
            imos[chan[i][k][1]+1]-=1

for i in range(1,10**5+2):
     imos[i] +=imos[i-1]  
print(max(imos))

Submission status: Accepted

Solution code:
N, Ch = map(int, input().split())
L = [list(map(int, input().split())) for i in range(N)]
L.sort(key=lambda x: x[0])
time = 0
T = [-1]
C = [-1]
ans = 1
for si, ti, ci in L:
    if time < si:
        time = si
        for xt, t in enumerate(T):
            if t == -1:
                continue
            elif t < si:
                T[xt] = -1
                C[xt] = -1
            elif t == si:
                T[xt] = -2

    if -2 in T:
        flg = False
        for index, t in enumerate(T):
            if t != -2:
                continue
            if C[index] == ci:
                T[index] = ti
                flg = True
                break
        if flg:
            continue

    if -1 in T:
        index = T.index(-1)
        T[index] = ti
        C[index] = ci
        continue
    else:
        ans += 1
        T.append(ti)
        C.append(ci)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import Counter
N,C = map(int,input().split())
link =[[] for _ in range(C+1)]
for i in range(N):
    x,y,c=[int(i) for i in input().split()]
    link[c].append((x,y))
siyou = np.array([0] * (C) * 100000).reshape(C,100000)
for i in range(1,C+1):
  for x,y in link[i]:
    siyou[i-1][x-1:y] = 1
print(np.max((np.sum(siyou, axis=0))))

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
program = []
program_list = [False for _ in range((((10 ** 5) * 2) + 10))]
for _ in range(C + 1):
    program.append(program_list.copy())

for _ in range(N):
    s, t, c = map(int, input().split())
    s2 = (t * 2) - ((s * 2) - 1)
    program[c][(s * 2) - 1:t * 2] = [True] * s2

max_c = 0
for i in range(len(program_list)):
    c = 0
    for j in range(1, C + 1):
        if program[j][i]:
            c += 1
        if c > max_c:
            max_c = c
print(max_c)

Submission status: Accepted

Solution code:
n,c = (int(i) for i in input().split())
x,y = [0 for i in range(100002)],[]
for _ in range(n):
	i,j,k = (int(l) for l in input().split())
	y.append([k,i,j])
y = sorted(y)
x[y[0][1]-1]+=1
x[y[0][2]]-=1
for i in range(1,n):
	if y[i][0]==y[i-1][0] and y[i][1]==y[i-1][2]:
		x[y[i][1]]+=1
		x[y[i][2]]-=1
	else:
		x[y[i][1]-1]+=1
		x[y[i][2]]-=1
for i in range(1,len(x)): x[i]+=x[i-1]
print(max(x))

Submission status: Accepted

Solution code:
import numpy as np
N,C = map(int,input().split())

f=[[0]*100000 for _ in range(C)]

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

arr = np.array(f)
print(np.max((np.sum(arr, axis=0))))

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
TV = [[0]*(2*10**5) for i in range(C)]

for i in range(N):
    s, t, c = map(int, input().split())
    TV[c-1][2*s-2] += 1
    TV[c-1][2*t-1] -= 1

for i in range(C):
    for j in range(1, 2*10**5):
        TV[i][j] = TV[i][j]+TV[i][j-1]

for i in range(C):
    for j in range(1, 2*10**5):
        TV[i][j] = min(1, TV[i][j])

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

Submission status: Accepted

Solution code:
n,c=[int(i) for i in input().split()]
s0=[]
t0=[]
for _ in range(n):
  a=[int(i) for i in input().split()]
  s0.append((a[0],a[2]))
  t0.append((a[1],a[2]))
s1=set(s0)
t1=set(t0)
s2=list(s1.difference(t0))
t2=list(t1.difference(s0))
s=[i[0]-0.5 for i in s2]
t=[i[0] for i in t2]

s.sort()
t.sort()
x=0
m=0
si=0
ti=0
while si != len(s):
  if s[si] < t[ti]:
    x+=1
    si+=1
  else:
    x-=1
    ti+=1
  m = max(m,x)
print(m)

Submission status: Accepted

Solution code:
#abc080d

N,C=map(int,raw_input().split())
l=[[0 for i in xrange(C)] for j in xrange(10**5)]
for i in xrange(N):
 s,t,c=map(int,raw_input().split())
 s-=1
 for j in xrange(s,t):
  l[j][c-1]=1

res=0
for i in xrange(10**5):
 if sum(l[i])>res:
  res=sum(l[i])
print res

Submission status: Accepted

Solution code:
def m():
    N, C = map(int, input().split())
    s = []
    t = []
    c = []
    for i in range(N):
        x, y, z = map(int, input().split())
        s.append(x)
        t.append(y)
        c.append(z)

    TIME = 100002
    recod = [[0 for _ in range(1, TIME+1)] for _ in range(1, C+2)]
    for n in range(N):
        for k in range(s[n], t[n]+1):
            recod[c[n]][k] = 1

    recodcnt = 1
    for n in range(TIME):
        tmp = 0
        for g in range(1, C+1):
            if recod[g][n] == 1:
               tmp += 1
        recodcnt = max(tmp, recodcnt)
    return recodcnt


print(m())

Submission status: Accepted

Solution code:
N,C = map(int,input().split())
A = [[0 for _ in range(C)] for j in range(100001)]
for i in range(N):
    s,t,c = map(int,input().split())
    for j in range(s-1,t):
        A[j][c-1] = 1
R = 0
for i in range(100001):
    sumA = sum(A[i])
    if R < sumA:
        R = sumA
print(R)

Submission status: Accepted

Solution code:
n,c = [int(i) for i in input().split()]

A = [[0 for i in range(c)] for j in range(100000)]
for i in range(n):
    s,t,c = [int(i) for i in input().split()]
    for i in range(s-1,t):
        A[i][c-1] = 1


ans = 0
for i in range(100000):
    val = sum(A[i])
    if val > ans:
        ans = val

print(ans)

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
ans=[[] for i in range(10**5*2+2)]
for i in range(N):
  s,t,c=map(int,input().split())
  if -c in ans[2*s]:
    d=ans[2*s].index(-c)
    ans[2*s].pop(d)
  else:
    ans[2*s-1].append(c)
  if c in ans[2*t-1]:
    d=ans[2*t-1].index(c)
    ans[2*t-1].pop(d)
  else:
    ans[2*t].append(-c)
timetable=[0 for j in range(200002)]
for i in range(10**5*2+2):
  for j in range(len(ans[i])):
    if ans[i][j]>0:
      timetable[i]+=1
    else:
      timetable[i]-=1
res=0
for i in range(1,200002):
  timetable[i]+=timetable[i-1]
  res=max(res,timetable[i])
print(res)

Submission status: Accepted

Solution code:
N, C = list(map(int, input().split()))
tmax = 0
s = [0 for _ in range(N)]
t = [0 for _ in range(N)]
c = [0 for _ in range(N)]
for i in range(N):
    s[i], t[i], c[i] = list(map(int, input().split()))

tmax = max(t)
c_timeline = [[0]*C for _ in range(2 * tmax + 1)]
for i in range(N):
    S = s[i]
    T = t[i]
    channel = c[i] - 1
    for j in range(2 * S - 1, 2 * T + 1):
        c_timeline[j][channel] = 1

time = [0 for _ in range(2*tmax+1)]
for timeline in c_timeline:
    time.append(sum(timeline))

print(max(time))

Submission status: Accepted

Solution code:
N, C = list(map(int, input().split()))
tmax = 0
s = [0 for _ in range(N)]
t = [0 for _ in range(N)]
c = [0 for _ in range(N)]
for i in range(N):
    s[i], t[i], c[i] = list(map(int, input().split()))

tmax = max(t)
c_timeline = [[0]*C for _ in range(2 * tmax + 1)]
for i in range(N):
    S = s[i]
    T = t[i]
    channel = c[i] - 1
    for j in range(2 * S - 1, 2 * T + 1):
        c_timeline[j][channel] = 1

rokuga = 0
for timeline in c_timeline:
    time = sum(timeline)
    if rokuga < time:
        rokuga = time

print(rokuga)

Submission status: Accepted

Solution code:
import numpy

N, C = map(int, input().split())
STC = [list(map(int, input().split())) for i in range(N)]
Channel = numpy.array([[0]*(2*10**5+1) for i in range(C+1)])

for s, t, c in STC:
    Channel[c][2*s-1] += 1
    Channel[c][2*t] -= 1
    
for i in range(len(Channel)):
    Channel[i] = numpy.cumsum(Channel[i])
bool_Channel = Channel.astype(numpy.bool_)

needs = numpy.sum(bool_Channel, axis=0)
print(needs.max())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc080/tasks/abc080_d

"""
import sys
from sys import stdin
from heapq import heappop, heappush, heappushpop
input = stdin.readline


def prep_programs(programs, C):
    # 同じチャンネルで連続録画する場合はまとめる
    channels = [[] for _ in range(C+1)]
    res = []

    programs.sort()
    for s, t, c in programs:    #  チャンネルごとに録画したい番組を分ける
        channels[c].append([s, t])

    for i in range(1, C+1):      #  zipでずらして処理できるように、ダミーの番組を追加
        channels[i].append([-1, -1])

    # チャンネルごとに連続する番組があれば一つの録画枠にまとめる
    for i in range(1, C+1):
        prev_start = channels[i][0][0]
        for a, b in zip(channels[i], channels[i][1:]):
            if a[1] == b[0]:
                pass
            else:
                res.append([prev_start, a[1], i])
                prev_start = b[0]
    res.sort()
    return res                  #  まとめた録画リスト


def solve(programs, N, C):
    P = prep_programs(programs, C)

    max_used = 1                #  必要な録画機の台数
    R = []

    heappush(R, 0)
    for s, t, c in P:
        end_time = heappushpop(R, t)
        if end_time >= s:       #  番組の録画時間になった時に前の番組が終わっていない (チャンネルが違う場合は、前の録画終了と次の録画開始が同時でも2台必要)
            heappush(R, end_time)
            max_used = len(R)
    return max_used


def main(args):
    programs = []
    N, C = map(int, input().split())
    for _ in range(N):
        s, t, c = map(int, input().split())
        programs.append([s, t, c])
    ans = solve(programs, N, C)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc080/tasks/abc080_d

"""
import sys
from sys import stdin
from heapq import heappop, heappush, heappushpop
input = stdin.readline


def prep_programs(programs):
    # 同じチャンネルで連続録画する場合はまとめる
    channels = [[] for _ in range(31)]
    res = []

    for s, t, c in programs:
        channels[c].append([s, t])

    for i in range(1, 31):
        channels[i].append([-1, -1])

    for i in range(1, 31):
        prev_start = channels[i][0][0]
        for a, b in zip(channels[i], channels[i][1:]):
            if a[1] == b[0]:
                pass
            else:
                res.append([prev_start, a[1], i])
                prev_start = b[0]
    return res


def solve(programs, N, C):
    programs.sort()
    programs = prep_programs(programs)
    programs.sort()

    max_used = 1
    R = []

    heappush(R, 0)
    for s, t, c in programs:
        end_time = heappushpop(R, t)
        if end_time >= s:
            heappush(R, end_time)
            max_used = len(R)
    return max_used


def main(args):
    programs = []
    N, C = map(int, input().split())
    for _ in range(N):
        s, t, c = map(int, input().split())
        programs.append([s, t, c])
    ans = solve(programs, N, C)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import accumulate
def inpl(): return tuple(map(int, input().split()))

N, C = inpl()
P = [[] for _ in range(C)]

for _ in range(N):
    s, t, c = inpl()
    P[c-1].append((2*s, 2*t))

S = [0 for _ in range(2*10**5 + 3)]
for p in P:
    if len(p) == 0:
        continue
    p2 = []
    p = sorted(p)
    s, t = p[0]
    for i in range(1, len(p)):
        if t == p[i][0]:
            t = p[i][1]
        else:
            S[s-1] += 1
            S[t+1] -= 1
            s, t = p[i]
    S[s-1] += 1
    S[t+1] -= 1

print(max(accumulate(S)))

Submission status: Accepted

Solution code:
def getter(starts, ends):
    while starts:
        if starts[-1][0] < ends[-1][1]:
            yield (starts.pop(), True)
        else:
            yield (ends.pop(), False)


def foo(C, targets):
    starts = sorted(targets, key=lambda x:x[0], reverse=True)
    ends = sorted(targets, key=lambda x: x[1], reverse=True)

    result = 0
    active = [0]*(C+1)
    for x, p in getter(starts, ends):
        if p:
            active[x[2]] += 1
        else:
            active[x[2]] -= 1
        result = max(result, sum(map(lambda x: 1 if x > 0 else 0 ,active)))
    return result


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-1, t, c))
    print(foo(C, targets))

Submission status: Accepted

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

chs = [[0] * (MAX_T + 1) for i in range(C)]
for i in range(N):
    chs[c[i]][s[i]] += 1
    chs[c[i]][t[i]] -= 1

ups = [0] * (MAX_T + 1)
downs = [0] * (MAX_T + 1)
for i in range(MAX_T):
    ups[i] = sum([chs[j][i] for j in range(C) if chs[j][i] > 0])
    downs[i] = sum([-chs[j][i] for j in range(C) if chs[j][i] < 0])

ans = 0
cur = 0
for i in range(MAX_T+1):
    cur += ups[i]
    ans = max((ans, cur))
    cur -= downs[i]

print(ans)

Submission status: Accepted

Solution code:
N,C = map(int,input().split())
stc = [[int(x) for x in input().split()] for _ in [0]*N]
st = []
for c in range(1,C+1):
    stlist = sorted([x for x in stc if x[2]==c])
    prevs = prevt = 0
    for s,t,c in stlist:
        if s != prevt:
            st.append((prevs,prevt))
            prevs = s
        prevt = t
    st.append((prevs,prevt))
st = sorted([x for x in st if x!=(0,0)])
rec = [0]
for _st in st:
    m= min(rec)
    if m<_st[0]:
        rec.remove(m)
    rec.append(_st[1])
print(len(rec))

Submission status: Accepted

Solution code:
def LI(): return list(map(int, input().split()))
def LS(): return input().split()
def I(): return int(input())
def S(): return input()

n, c = LI()
l = []
for i in range(n):
    l.append(LI())

#チャンネル見る必要がある
#同じチャンネルで連続しているものはくっつける
la = [[[], []] for i in range(c)]
for i in l:
    la[i[2] - 1][0].append(i[0])
    la[i[2] - 1][1].append(i[1])

starts = []
ends = []
for s, e in la:
    wa = set(s).union(set(e))
    seki = set(s).intersection(set(e))
    a = list(wa.difference(seki))
    a.sort()
    for i, j in zip(a[0::2], a[1::2]):
        starts.append(i)
        ends.append(j)

s = min(starts)
e = max(ends)

imos = [0 for i in range(s,e + 2)]
for i, j in zip(starts, ends):
    imos[i - s] += 1
    imos[j - s + 1] -= 1
for i in range(len(imos) - 1):
    imos[i + 1] += imos[i]

print(max(imos))

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
f = [[0] * 100001 for _ in range(C)]

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

print(max(map(sum, zip(*f))))

Submission status: Accepted

Solution code:
n, c = map(int, raw_input().split())
time_table = [list(map(int, raw_input().split())) for _ in xrange(n)]
time_table.sort()

recoders = [[True for i in xrange(10**5+1)]]
for tt in time_table:
    for recoder in recoders:
        if recoder[0] == tt[2]:
            for i in xrange(tt[0], tt[1]+1):
                recoder[i] = False
            break
        else:
            if recoder[tt[0]]:
                for i in xrange(tt[0], tt[1]+1):
                    recoder[i] = False
                recoder[0] = tt[2]
                break
    else:
        recoders.append([True for i in xrange(10**5+1)])
        recoders[-1][0] = tt[2]
        for i in xrange(tt[0], tt[1]+1):
            recoders[-1][i] = False
print len(recoders)

Submission status: Accepted

Solution code:
import collections
N,C=map(int,raw_input().split())
a=collections.defaultdict(list)

max_t=0
for i in range(N):
	s,t,c=map(int,raw_input().split())
	a[c].append((s,t))
	max_t=max(max_t,t)

[a[i].sort() for i in a.keys()]
#print a
#print max_t

b=collections.defaultdict(list)


for i,j in a.items():
	start=0
	end=0
	for k in j:
		if start==0 and end==0:
			start=k[0]-1
			end=k[1]
			continue
		elif k[0]<=end:
			end=k[1]
		else:
			b[i].append((start,end))
			start=k[0]-1
			end=k[1]
	else:
		b[i].append((start,end))		

#print "# b"
#print b

c=[0 for i in range(max_t+2)]

for i in b.values():
	for j,k in i:
		#print j,1,k+1,-1
		c[j]+=1
		c[k]-=1
#print c

ans=0
sum=0
for i in c:
	sum+=i
	ans=max(ans,sum)

print ans

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

N,C=[int(i) for i in input().split()]
stc=[list(map(int,input().split())) for i in range(N)] #N行分の入力を二重配列にする

sort_stc = sorted(stc)

#print(sort_stc)

counter = 0
rokuga_joutai = []
for bangumi in range(N):
    flag = -1
    for rokugaki in range(counter):
        if ((rokuga_joutai[rokugaki][2] == sort_stc[bangumi][2] and rokuga_joutai[rokugaki][1]-0.1 < sort_stc[bangumi][0]) or rokuga_joutai[rokugaki][1] + 0.5 < sort_stc[bangumi][0]):
            flag = rokugaki
    if flag != -1:
#        print(flag)
        rokuga_joutai[flag][0] = sort_stc[bangumi][0]
        rokuga_joutai[flag][1] = sort_stc[bangumi][1]
        rokuga_joutai[flag][2] = sort_stc[bangumi][2]
    else:
        rokuga_joutai.append([sort_stc[bangumi][0],sort_stc[bangumi][1],sort_stc[bangumi][2]])
        counter += 1
#    print(rokuga_joutai)
print(counter)

Submission status: Accepted

Solution code:
L = 100005
 
n,c = map(int, input().split())
 
arr = [[0]*L for j in range(c)]
for _ in range(n):
    s,t,col = map(lambda x:int(x)-1, input().split())
    arr[col][s] += 1
    arr[col][t] -= 1
 
imos = [0]*L
 
for i in range(c):
    for p in range(L):
        if arr[i][p] == 1: imos[p] += 1
        if arr[i][p] == -1: imos[p+1] -= 1
 
ans = 0
for i in range(1,L):
    imos[i] += imos[i-1]
    ans = max(ans, imos[i])
 
print(ans)

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
 
f = [[0] * 100000 for _ in range(C)]
 
for i in range(N):
    s, t, c = map(int, input().split())
    f[c-1][s-1:t] = [1] * (t-s+1)
 
print(max(map(sum, zip(*f))))

Submission status: Accepted

Solution code:
import sys

def main():
    n, c = getLineInts()
    ss = [0 for i in range(n)]
    ts = [0 for i in range(n)]
    cs = [0 for i in range(n)]
    ics = [[] for c in range(31)]
    for i in range(n):
        ss[i], ts[i], cs[i] = getLineInts()
        ics[cs[i]].append(i)
        
    icms = []
    for c in range(31):
        prepS = None
        prepT = None
        for i in sorted(ics[c], key = lambda i: ss[i]):
            if prepS is not None and prepT == ss[i]:
                prepT = ts[i]
            else:
                if prepS is not None:
                    icms.append((prepS, 0))
                    icms.append((prepT, 1))
                prepS = ss[i]
                prepT = ts[i]
        if prepS is not None:
            icms.append((prepS, 0))
            icms.append((prepT, 1))
    
    vMax = 0
    cur = 0
    icms = sorted(icms, key = lambda e: e[1])
    icms = sorted(icms, key = lambda e: e[0])
    for (t, type) in icms:
        if type == 0:
            cur += 1
            if vMax < cur:
                vMax = cur
        else:
            cur -= 1
    print(vMax)


def getLineInts():
    return [int(x) for x in sys.stdin.readline().rstrip().split(' ')]


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict as ddict
N, C = map(int, input().split())
imos = [0] * (10**5 + 2)
last_s_by_c = ddict(lambda: 1)
last_t_by_c = ddict(int)
stc = [list(map(int, input().split())) for i in range(N)]
for s, t, c in sorted(stc, key=lambda x: x[1]):
	if last_t_by_c[c] != s:
		imos[last_s_by_c[c] - 1] += 1
		imos[last_t_by_c[c]] -= 1
		last_s_by_c[c] = s
	last_t_by_c[c] = t
for c in last_s_by_c:
	imos[last_s_by_c[c] - 1] += 1
	imos[last_t_by_c[c]] -= 1
for i in range(10**5 + 1):
	imos[i + 1] += imos[i]
print(max(imos))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
f=[[0]*int(1e5) for _ in range(C)]

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

print(max(map(sum,zip(*f))))

Submission status: Accepted

Solution code:
N, C = map(int, input().split())

f = [[0] * 100000 for _ in range(C)]

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

print(max(map(sum, zip(*f))))

Submission status: Accepted

Solution code:
import sys

#入力行から整数として受け取る
def ReadLineInt():
    return [int(x) for x in sys.stdin.readline().split()]

n, c = ReadLineInt()

#働いているレコーダーは、その録画の終わる時間が記録される
recorders = [-1] * (c+1)

#ソートすることで、レコーダーのリストで録画されているものは全て自分よりも前から動いている。
programs = sorted([ReadLineInt() for _ in range(n)])

#プログラムの始まる時間よりもレコーダーの稼働が終わる時間が遅いときは、そのレコーダーは使えない
for start, end, channel in programs:
    for i in range(c):
        if recorders[i] < start:
            recorders[i] = end
            break

ans = 0

#最終的に終わる時間が記録されているレコーダーは使ったということで、何台のレコーダーが同時に使われたかを答えとして返す。
for i in range(c+1):
    if recorders[i] < 0:
        ans = i
        break

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
 
sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7
 
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()
def pf(s): return print(s, flush=True)
 
 
def main():
    n,c = LI()
    a = [-1] * (c+1)
    b = sorted([LI() for _ in range(n)])
    for s,t,d in b:
        for i in range(c):
            if a[i] < s:
                a[i] = t
                break
 
    for i in range(c+1):
        if a[i] < 0:
            return i
 
    return -1
 
 
 
print(main())

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

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()
def pf(s): return print(s, flush=True)


def main():
    n,c = LI()
    a = [-1] * (c+1)
    b = sorted([LI() for _ in range(n)])
    for s,t,d in b:
        for i in range(c):
            if a[i] < s:
                a[i] = t
                break

    for i in range(c+1):
        if a[i] < 0:
            return i

    return -1



print(main())

Submission status: Accepted

Solution code:
N,C = [int(val) for val in raw_input().split(" ")]

table = [[0]*(10**5) for i_c in range(C)]

for i_n in xrange(N):
    s_i, t_i, c_i = [int(val) for val in raw_input().split(" ")]
    for loc in xrange(s_i-1, t_i-1):
        table[c_i-1][loc] = 1
    if s_i>1:
        table[c_i-1][s_i-2] = 1

req = 0
for loc in xrange(10**5):
    tmp = sum([table[i_c][loc] for i_c in xrange(C)])
    if tmp > req:
        req = tmp

print req

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
S = []
for i in range(N):
    S.append(list(map(int, input().split())))
S.sort()
R = [[] for i in range(C)]
for i in range(N):
    c = S[i][2] - 1
    if R[c]:
        if R[c][-1][1] == S[i][0]:
            R[c][-1][1] = S[i][1]
            continue
    R[c].append(S[i][:])
D = [0]*100001
for r in R:
    for s in r:
        for i in range(s[0], s[1]+1):
            D[i] += 1
print(max(D))

Submission status: Accepted

Solution code:
def func():
    tvs = []
    for i in range(num):
        tvs.append((-1, -1))
    for i in range(len(bans)):
        now = bans[i][0]
        can = bans[i][2]
        # tvs = [tv for tv in tvs if tv[1] == can] + [tv for tv in tvs if tv[1] != can]
        for j, tv in enumerate(tvs):
            if tv[1] == -1 or (tv[1] == can and tv[0] <= now) or tv[0] <= now - 1:
                del tvs[j]
                tvs.append((bans[i][1], can))
                break
        else:
            return False
    return True


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

bans = []
for i in range(n):
    bans.append(tuple(map(int, input().split())))
bans.sort(key=lambda x: x[0])

for num in range(1, 1024):
    if func():
        print(num)
        break

Submission status: Accepted

Solution code:
def func():
    tvs = []
    for i in range(num):
        tvs.append((-1, -1))
    for i in range(len(bans)):
        now = bans[i][0]
        can = bans[i][2]
        tvs = [tv for tv in tvs if tv[1] == can] + [tv for tv in tvs if tv[1] != can]
        for j, tv in enumerate(tvs):
            if tv[1] == -1 or (tv[1] == can and tv[0] <= now) or tv[0] <= now - 1:
                del tvs[j]
                tvs.append((bans[i][1], can))
                break
        else:
            return False
    return True


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

bans = []
for i in range(n):
    bans.append(tuple(map(int, input().split())))
bans.sort(key=lambda x: x[0])

for num in range(1, 1024):
    if func():
        print(num)
        break

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""abc080_d"""


import sys


def main():
    """Main function."""
    N, C = map(int, input().split(' '))
    table = [[0]*100000 for _ in range(C)]

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

    print(max(map(sum, zip(*table))))


if __name__ == '__main__':
    sys.exit(main())

Submission status: Accepted

Solution code:
def d_recording(N, C, R):
    """
    N:録画する番組の数
    C:テレビが受信できるチャンネルの数
    R:録画する番組の情報 [開始時刻s,終了時刻t,チャンネルc]
    """
    s = [row[0] for row in R]
    t = [row[1] for row in R]
    c = [row[2] for row in R]

    # いつまで録画機を動かすか。0.5を単位時間とするので*2
    # 時刻を0からスタートさせるので+2
    l = max(t) * 2 + 2
    sm = [0 for _ in range(l)]  # ある時刻に動いている録画機の数が格納される

    for i in range(1, C + 1):
        tt = [0 for _ in range(l)]  # チャンネルiを録画しているか否かを格納
        # 累積和を取る
        for j in range(N):
            if c[j] == i:
                # 録画開始時刻の0.5前を+1,終了時刻を-1
                #(終了時刻は含まないという録画機の条件より、このようにする)
                tt[s[j] * 2 - 1] += 1
                tt[t[j] * 2] -= 1
        for j in range(1, l):
            tt[j] += tt[j - 1]
        # あるチャンネルを録画している時間帯では、録画機を1個使わねばならない
        for j in range(l):
            if tt[j] > 0:
                sm[j] += 1
    ans = max(sm)
    return ans

N,C = [int(i) for i in input().split()]
R = [[int(i) for i in input().split()] for j in range(N)]
print(d_recording(N, C, R))