1931번:회의실 배정

18 Aug 2022 in PS on Ps

문제

코드

s=[]
f=[]
arr=[]
N=int(input(""))
for i in range(N):
    A,B=map(int,input("").split())
    arr.append([A,B])

arr.sort(key=lambda x:x[0])
arr.sort(key=lambda x:x[1])

for x,y in arr:
    s.append(x)
    f.append(y)
A=[0]
j=0

for i in range(1,N):
    if(s[i]>=f[j]):
        A.append(i)
        j=i
print(len(A))

설명

greedy방식으로 회의시간이 제일 먼저 끝나는 시각 기준으로 알고리즘을 풀어감
위에 설명한 기준으로 오름차순 정렬
제일빠른 시각에 끝나는 회의가 포함되기때문에 0 idx가 A에 기본적으로 존재
회의 종료 시각이 가장 빠른 회의가 optimal solution의 항상 존재하는 이유

후기

2차원 리스트의 정렬을 배울수 있어서 좋았다
회의 시간이 겹치지 말라해서 같은시간이 두 번 들어올때까지 고려해서 시간초과났었음 EX) 4-4,4-4
사실 아직 기준선정에 있어서 의아함이 풀리지 않은 상태