[CodingTest] BOJ1931 회의실 배정 ( greedy ) With 파이썬

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

1931번: 회의실 배정

 

 

◎ 문제풀이

 

한 개의 회의실을  최대로 이용할 수 있는 회의의 개수를 구하는 문제이다. 끝나는 시간이 기준이다. 회의가 언제 끝나는지를 알아야 무엇을 시작할지가 결정된다. 그러므로 가장 빨리 끝나는 것부터 하나씩 회의실을 잡으면 된다.

 

그래서 정렬을 활용하여 문제를 풀었더니 한 가지 반례가 있었다. 

 

2
9 9
1 9

 

끝나는 시간을 기준으로 하면 위 반례를 커버하지 못한다. 둘 다 똑같이 9시에 끝나지만 시작시간이 다르다.  그러므로 아래와 같이 풀면 된다.

 

1) 시작시간으로 먼저 정렬한다. 

시작시간으로 정렬하면 같은 종료시간인 회의는 시작순으로 정렬된다. 

 

2) 시작순으로 정렬된 리스트를 다시 종료시간으로 정렬한다.

기준은 종료시간이므로 종료시간으로 정렬하면 위 반례가 커버된다. 

 

meetings = sorted(meetings,key=lambda time : time[0]) # 시작순으로 정렬
meetings = sorted(meetings,key=lambda time : time[1]) # 종료순으로 정렬

 

두 가지 정렬을 하나로 표현할수 있다. 

 

meetings = sorted(meetings,key=lambda time : (time[1],time[0]))
#(time[1],time[0]) (종료시간,시작시간)

 

◎ 코드

import sys
input = sys.stdin.readline

n = int(input())
meetings = [[] for _ in range(n)]

for i in range(n) :
  start,end = map(int,input().split())
  meetings[i] = [start,end]

meetings = sorted(meetings,key=lambda time : (time[1],time[0]))

count = 1
end = meetings[0][1]
for i in range(1,n) :
  if end > meetings[i][0] : continue
  end = meetings[i][1] 
  count+=1

print(count)

 

---

참고자료

[백준알고리즘] 1931번: 회의실배정 -Python