[백준][PYTHON] 1931번 회의실 배정

문제 설명

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

 

그리디 알고리즘에 관한 문제이다. 

 

문제 접근

문제는 각 회의가 겹치지 않게 하면서 가장 많은 회의의 개수를 찾는 것이다. 

어떻게 해야할까?

 

1. 회의 시작 시간을 기준으로 가장 빠른 회의 선택

: 이 경우 회의 시작 시간은 빠르지만, 진행 시간이 길다면 다른 회의를 선택하지 못하므로 옳지 않다. 

ex) (0, 10) 과 (1, 2), (2, 4) 가 있으면, (0, 10)은 좋지 않은 선택지이다. 

 

2. 회의 진행 시간이 짧은 기준으로 선택

: 회의 진행 시간에 따라 정렬을 하면, 시작시간과 종료시간이 뒤죽박죽된다. 

ex) (0, 3), (1, 5), (2, 3) -> (2, 3), (0, 3), (1, 5)

 

3. 회의 종료 시간을 기준으로 가장 빠른 회의 선택

: 회의 종료 시간을 기준으로 회의를 정렬하고, 이 배열을 순차적으로 확인하면서 

1번 회의 종료 -> 다음 회의 중 회의 종료 시간이 가장 빠른 회의 선택

* 다만 이 과정에서 회의 종료 시간을 기준으로 먼저 정렬을 하고, 그 다음 정렬 기준으로 회의 시작 시간을 지정한다. 

즉, 1) 끝나는 시간 오름차순 / 2) 시작하는 시간 오름차순

으로 정렬을 진행한다. 

 

조금 더 자세한 예를 들어보자. 
(0, 10), (3, 4), (2, 3), (1, 2) 와 같은 회의가 있을 때
회의 종료 시간이 빠른 순서대로 정렬을 하면
(1, 2), (2, 3), (3, 4), (0, 10)으로 정렬이 된다. 

또한, 여기서 회의 종료 시간이 같을 경우 먼저 시작하는 회의를 기준으로 정렬이 되어야 한다. 
즉, (2, 2), (1, 2)의 회의가 있을 때
(2, 2)가 먼저 선택되면 (1, 2)는 (2, 2)의 끝나는 시간보다 시작시간이 일찍되기 때문에 무시되어 1번의 회의만 진행된다. 
그러나, 정렬을 통해 (1, 2)가 먼저 선택되면 (2, 2)도 선택이 가능하므로 가능한 회의는 2번이 된다. 

 

정답 코드

# input 입력받기
N = int(input())

conf = []
for _ in range(N):
    conf.append(list(map(int, input().split())))
# print(conf) [[1, 4], [3, 5], [0, 6], [5, 7], ..]

# 끝나는 시간의 오름차순 -> 시작하는 시간의 오름차순
conf = sorted(conf, key = lambda x: (x[1], x[0]))

# print(conf) [[1, 4], [3, 5], [0, 6], ..
answer = 0
tmp = 0         # 회의가 끝나는 시간을 나타냄
for start, end in conf:
    # 회의 시작 시간이 앞선 회의가 끝나는 시간보다 크면 회의 가능
    if start >= tmp:
        answer += 1
        # 현재 회의가 끝난 시간을 tmp에 업데이트
        tmp = end
        
print(answer)

 

앞서 말한대로 회의 리스트들을 정렬하고, 

회의가 끝나는 시간을 명시할 변수 tmp를 지정한다. 

이를 기준으로 하나의 회의의 시작 시간이 앞선 회의가 끝나는 시간보다 크다면 회의가 가능하기 때문에

회의 가능 횟수를 증가시킨다. 

그 후, 현재 회의가 끝난 시간을 tmp에 업데이트하며 모든 회의를 순회한다.