[백준 1931번] 회의실 배정 - 파이썬

 

문제 출처:

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

1931번: 회의실 배정

 

회의실 배정 문제에서 가장 중요한 문장은 " 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. "이다.

해결 방법은 그리디 알고리즘과 정렬을 이용하면 된다.

 

 

첫 번째 아이디어: 회의 시간마다 끝나는 시간을 기준으로 오름차순 정렬한 다음에

다음 회의 시작 시간이 >= 회의 끝 나는 시간이라면 최적의 해를 도출할 수 있을까?

하지만 다음과 같은 상황을 고려해야 한다.

(1, 5)

(5, 7)

(5, 6)

 

위와 같이 입력을 받았다면 (1, 5) 회의 끝난 다음에 (5, 7)이 회의를 진행할 것이다. 그러나 (5,7)보다 (5, 6)이 회의 진행 시간이 짧으며 이는 최적의 해를 도출할 수 없다.

 

 

따라서 1. 회의 시간마다 끝나는 시간을 기준으로 오름차순 정렬 2. 시작하는 시간 오름차순으로 정렬이 이루어져야 한다. 

(2차원 이상의 데이터를 정렬해야 한다면 sort(key=lambda x: ( ) )를 이용하면 된다.

1차원 데이터일 경우에는 sort( )를 이용하면 된다.)

 

이제 그리디 알고리즘과 정렬을 이용해 코드를 작성해보자.

#1931번 회의실 배정
#1. 끝나는 시간 오름차순, 시작 시간 오름차순 정렬
#2. 다음 회의 시작 시간이 직전의 회의 끝 시간보다 크거나 같으면 회의 가능

n = int(input())

data = [[0]*2 for _ in range(n)]

for i in range(n):
    s, e = map(int, input().split())
    data[i][0] = s
    data[i][1] = e


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


# 첫번째로 회의 사용
end_time = data[0][1]
count = 1

# 회의의 최대 개수 출력하기
for j in range(1, n):
  start_time = data[j][0]
  # 회의 시작이 전 회의 종료 시간보다 크거나 같으면 회의실 사용 가능
  if start_time >= end_time:
    count += 1
    end_time = data[j][1]

# 회의의 최대 개수 출력
print(count)

 

[백준 1931번] 회의실 배정 - 파이썬