[ 백준/python ] 1931 : 회의실 배정

- 문제

 

- 제출

이 문제를 처음 봤을 때는, 당연히 시작하는 시간을 기준으로만 생각했다. 시작 시간이 작은 순서대로 배열하고 시작 시간이 같다면 끝 시간이 작은 순서대로 배열하여 비교해가며 정렬하면 최대 횟수가 나올 것이라고 생각했다.

하지만 계속 생각을 해도 어디엔가 오류가 있었다.

 

따라서 반대로 끝나는 시간을 기준으로 생각해봤다. 끝나는 시간을 기준으로 배열하고 끝나는 시간이 같다면 시작하는 시간을 기준으로 배열하였다. 끝나는 시간이 빠를수록 같은 시간 범위 내에 많은 미팅 횟수를 넣을 수 있다. 따라서 끝나는 시간이 우선 기준이 되어야 한다.

배열을 마쳤다면, 가장 빠른 시간에 끝나는 미팅으로 end 값을 초기화하고 미팅을 한 번 시행했다고 카운팅한다.

그 후, 이전 미팅이 마친 시간과 다음 끝나는 시간이 짧은 미팅의 시작 시간을 비교하여 시작 시간이 더 큰 경우, 그 미팅의 끝나는 시간으로  end 값을 업데이트하고 미팅 횟수를 증가시킨다.

 

N = int(input())
meetings = []

for _ in range(N):
    a,b = map(int, input().split())
    meetings.append([a,b])
    
meetings.sort(key = lambda x: (x[1],x[0])) # end time 기준으로 먼저 정렬하는 것이 중요


end = meetings[0][1]
cnt = 1 # 첫 번째는 먼저 카운트
for i in range(1,N):
        if meetings[i][0] >= end:
            end = meetings[i][1]
            cnt +=1

print(cnt)

 

그리디 문제로 넣어 둔 문제 중에 가장 낮은 정답률의 문제인 만큼 상당히 어려웠다..

어떤 값을 정렬할 때 더 우선으로 할지를 알아내는 것이 중요했다!!