[백준]1931번 회의실 배정 - 그리디

 

n = int(input())
a = [[1]*2 for i in range(n)]
cnt = 0
check = 0

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

for i in range(n):
    if a[i][0] >= check:
        cnt += 1
        check = a[i][1]
        
print(cnt)

 

코드 설명

먼저 회의의 수를 위한 n, 회의의 정보를 위한 a 리스트, 회의의 최대 개수를 위한 cnt, 끝나는 시간을 체크하기 위한 check 변수를 선언한다. 그 후 회의 수 만큼 반복문을 통해 a 리스트에 회의의 정보를 전부 할당한 후, 정렬 함수를 통하여(lambda 사용) 끝나는 시간 순으로 정렬하고 그 뒤 기준은 시작 시간으로 하여 정렬한다. 

check 변수를 이용하여 만약 끝나는 시간보다 값이 크다면 중복이 되지 않으므로 이용할 수 있기에 cnt 를 1 증가시켜주고, check 변수의 값을 재 설정해준다.

 

Point : 회의의 끝나는 시간이 가장 적은 것이 중요하기에, 이를 기준으로 정렬을 하여야 한다. 그 뒤에는 끝나는 시간보다 시작시간이 작으면 회의실을 이용할 수 없기에 그 부분에서 통과되는 것만 카운트하면 최대 회의수를 구할 수 있게 된다.