파이썬 백준 : 1931 회의실 배정

문제

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

1931번: 회의실 배정

 

 

풀이

회의를 최대한 많이 진행하려면 회의가 빨리끝나는 순서대로 진행하면 된다! (회의가 빨리 끝나게 되면 그 이후 진행할 수 있는 회의의 경우의 수가 많기 때문)

 

1. 회의 시간을 2차원 list로 입력받는다 [[회의1 시작시간,회의1 종료시간], [회의2 시작시간,회의2 종료시간] ...]

2. 회의 종료시간을 기준으로 정렬한다

3. 정렬된 리스트를 순서대로 탐색하며 이전 회의의 종료시간보다 시작시간이 늦거나 같은경우(한 회의가 끝나는 것과 동시에 다음회의가 시작될수 있다) 회의를 진행한다

import sys
N=int(sys.stdin.readline())
clock = []
for _ in range(N):
    start, end=map(int, sys.stdin.readline().split())
    clock.append([start, end])
clock=sorted(clock,key=lambda x: (x[1], x[0])) #끝나는 시간을 기준으로 정렬
cnt=0 #진행되는 회의의 개수
meeting_end=clock[0][0]

for start,end in clock:
    if start>=meeting_end:#회의가 끝나는 시간이후에 시작하는 회의일경우 -> 회의 진행
        cnt+=1
        meeting_end=end #회의가 끝나는 시간 업데이트
print(cnt)