[BOJ] 1931. 회의실 배정

문제

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

 

 

 

---

 

주요 아이디어

이전에 풀었던 그리디 문제 (요격 시스템, 단속 카메라) 와 비슷한 유형이다!

1. 끝나는 시간을 기준으로 오름차순 정렬을 진행한다.

1-1. 이 때, 끝나는 시간이 같을 경우 시작 시간이 빠른 회의를 우선적으로 배치해야 최대 개수 탐색이 가능하므로 2차 정렬 기준을 시작 시간으로 잡는다.

 

반례 예제 : 

시작하자마자 끝나는 회의 input 이 잡힐 경우 에러가 발생하는데,

4
2 2
1 2
2 3
3 4

x[1] 기준 정렬 : [(2, 2), (1, 2), (2, 3), (3, 4)]

이런 경우 그리디하게 앞에서부터 탐색하면  (2,2)가 빠지게 되므로, 시작 시간이 빠른 회의를 우선적으로 배치해야 한다.

 

 

2. 이전 미팅 시작 시간이 현재 미팅 시작 시간보다 작다면

현재 미팅 끝 시간이 더 작은 것이 이미 오름차순 정렬로 보장되어 있으므로 시작과 끝이 모두 겹치지 않는다.

 

3. 현재 미팅 시간으로 갱신해준다. 

 

 

 

---

 

코드 구현 (Python 3)

n = int(input())
answer = 0
meetings = []

for i in range(n):
    s, e = map(int, input().split())
    meetings.append((s,e))

# 끝나는 순 기준 오름차순 정렬
# 반복문에서 i-1 회의가 끝나는 시간이 i 회의보다 빠름을 보장
# meetings.sort(key = lambda x: x[1])


# 끝나는 시간이 같을 경우 시작 시간이 빠른 회의를 우선적으로 배치
meetings.sort(key = lambda x: (x[1], x[0]))

meeting_start = 0

for x in meetings:
    # 이전 미팅 시작 시간이 현재 미팅 시작 시간보다 작다면
    if meeting_start <= x[0]:
        # 미팅 룸 안잡혀있으므로 answer 추가
        answer += 1
        meeting_start = x[1] # 시작 시간 갱신

print(answer)

 

 

 

제출 결과

 

---

관련 문제

https://ll2ll.tistory.com/93

[프로그래머스] 단속 카메라

https://ll2ll.tistory.com/94

[프로그래머스] 요격 시스템