[ 백준 ] 1931번 : 회의실배정 (파이썬)

문제 )

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

1931번: 회의실배정

 

[ 풀이 ]

Greedy Algorithm으로 풀어야 할 거 같긴 한데, 무엇을 기준으로 최적의 solution을 선택할 것인지 한참을 고민했다. 

고민 끝에 회의가 끝나는 시간을 기준으로 잡았다. 
회의가 끝나는 시간을 기준으로 회의시간이 있는 list를 정렬시키고 
" 회의가 끝나는 시간 <=  다음 회의가 시작하는 시간 "이 가능한 case들 중 
( 전 회의가 끝나는 시간 ~ 다음 회의가 시작하는 시간 ) 사이의 텀이 가장 짧은 회의를 선택한다. 

 

 

그러나, 여기서 주의해야 할 점은 
timelist=[[2,5],[3,7],[3,5],[2,2],[1,2]] 라고 가정했을 때 
그냥 종료 시간 ( timelist[1] ) 을 기준으로 정렬한다면 

timelist=[[2,5],[3,7],[3,5],[2,2],[1,2]]
timelist.sort(key=lambda x:x[1])
print(timelist)
# result = [[2, 2], [1, 2], [2, 5], [3, 5], [3, 7]]

result = [[2, 2], [1, 2], [2, 5], [3, 5], [3, 7]]  으로
시작 시간 ( timelist[0] ) 의 값들은 정렬되어있지 않은 상태이다 

 

그러므로,  
(1) 시작 시간 ( timelist[0] ) 기준 정렬 
(2) 종료 시간 ( timelist[1] ) 기준으로 정렬 해줘야 한다.

timelist=[[2,5],[3,7],[3,5],[2,2],[1,2]]
timelist.sort(key=lambda x:x[0])
timelist.sort(key=lambda x:x[1])
print(timelist)
# result = [[1, 2], [2, 2], [2, 5], [3, 5], [3, 7]]

 

< roomcount Function의 Algorithm >

✔ 회의의 시작시간, 종료시간이 들어있는 list → timelist 
✔ 사용가능한 회의실의 갯수 → count 
✔ 회의실 사용 가능한 시간 → start_time

1. timelist를 시작 시간을 기준으로 정렬해준다
2. timelist를 종료 시간을 기준으로 정렬해준다
3. timelist의 원소들에 하나씩 접근한다 → mt (하나의 list : [ 시작시간, 종료시간 ] ) 
              3-1)        
              If 회의(mt) 시작 시간 > start_time이면 회의실을 사용 가능하다는 의미
                        Ⅰ. count를 하나 더해준다
                        Ⅱ. start_time을 회의(mt)의 종료시간으로 바꿔준다 

 

- python code

import sys
input= sys.stdin.readline

def roomcount(timelist):
    timelist.sort(key=lambda x:x[0]) #sort by start time 
    timelist.sort(key=lambda x:x[1]) #sort by finish time 
    count=0
    start_time=0 #회의실 사용 가능한 시간
    for mt in timelist:
        if mt[0] >=start_time:
            count+=1
            start_time=mt[1] # start_time을 회의(mt)의 종료시간으로 바꾸기
    print(count)


N=int(input())
timelist=[]
for i in range(N):
    time=list(map(int,input().split()))
    timelist.append(time)
roomcount(timelist)