[백준] 1931 - 회의실 배정 (그리디 알고리즘)

와우 시간초과 대박

[시간초과 요인 분석]

- 이전의 코드는 O(n^2)였지만 O(n)으로 줄어들었다.

- 정렬을 한번 더 했어야 했다.

- 바로 머릿속에 있는대로 구현하기보다는 (모든것을 확인하려고 했었음), 불필요한것은 덜어낸 채로 찾아보는 방법을 더 생각해 보도록 하자.(시간초과와 관련이 있음)

#회의 시작시간 순으로 배열을 정렬한다.

sch=sorted(sch,key = lambda x: [x[1], x[0]])

 

[처음 코드]

import sys

n=int(sys.stdin.readline())
sch=[]

#회의의 시작시간 S , 마치는시간 E 를 sch 배열에 담는다.
for i in range(n):
    S,T=map(int,sys.stdin.readline().split())
    sch.append([S,T])

#회의 시작시간 순으로 배열을 정렬한다.
sch=sorted(sch,key = lambda x: [x[1], x[0]])

#print(sch)
cnt_list=[]
for i in range(n):
    cnt=1
    start_time=sch[i][0]
    end_time=sch[i][1]
    for j in range(i,n):
        if end_time==sch[j][0]:
            cnt+=1
            end_time=sch[j][1]
        elif end_time<=sch[j][0]:
            start_time=sch[j][0]
            end_time=sch[j][1]
            cnt+=1
    cnt_list.append(cnt)

print(max(cnt_list))

[수정 코드]

import sys

n=int(sys.stdin.readline())
sch=[]

#회의의 시작시간 S , 마치는시간 E 를 sch 배열에 담는다.
for i in range(n):
    S,T=map(int,sys.stdin.readline().split())
    sch.append([S,T])

#회의 시작시간 순으로 배열을 정렬한다.
sch=sorted(sch,key = lambda x: [x[1], x[0]])

#print(sch)
cnt_list=[]
cur_time=0
cnt=0
for i in range(n):
    if cur_time==sch[i][0]:
        cnt+=1
        cur_time=sch[i][1]
    elif cur_time<sch[i][0]:
        cnt+=1
        cur_time=sch[i][1]
print(cnt)