[알고리즘] 백준 1931 회의실 배정 (파이썬 풀이)

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

해결코드

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

cnt = 1
end = li[0][1]
for i in range(1,n):
    if li[i][0] >= end:
        cnt += 1
        end = li[i][1]

print(cnt)

문제풀이

처음에 보고 dfs문제인가? 했다가 정렬 문제인걸 알았다.

회의 시작 시간과 끝 시간이 주어지는데, 시간이 안겹치게

최대의 회의를 진행하려면 회의 끝나는 시간을 오름차순으로 정렬하여

순서대로 비교해보면 된다.

 

예를 들어 정렬했을 때 첫 회의가 1시부터 4시까지라면 다음 회의 시작 시간이

4시보다 크거나 같으면 된다.

 

코드를 보자

 

n = int(input())
li = [[0]*2 for _ in range(n)]

n에 회의 수를 입력받고

li에는 원소 두개를 가진 n개의 리스트를 담은 리스트를 배정한다.

 

for i in range(n):
    a,b = map(int, input().split())
    li[i][0] = a
    li[i][1] = b

n개만큼 for문을 실행시킨다.

a,b를 띄어쓰기하여 입력받고

li에 각각 삽입한다.

ex) li = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]

 

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

리스트 li를 정렬해준다(두번째 인자 기준으로 먼저 정렬 후 첫번째 인자 정렬)

x[0]도 정렬해주는 이유는 전 회의 끝나는 시간과 다음 회의 시작 시간이 같을 수도 있기 때문이다.

 

cnt = 1
end = li[0][1]

cnt는 1이라고 정해주고

첫 회의끝나는 시간은 li[0][1]값(리스트 첫 값)으로 해준다.

 

for i in range(1,n):
    if li[i][0] >= end:
        cnt += 1
        end = li[i][1]

1부터 n-1까지 for문을 실행시킨다.

만약 다음 회의 시작 시간이 전 회의 끝 시간과 크거나 같다면

cnt값을 +1해준다.

그리고 end값을 다음 회의 끝 시간으로 정해준다.

 

print(cnt)

cnt를 출력해준다.