프로그래밍/백준

[알고리즘] 백준 1931 파이썬 - 회의실 배정

매 석 2023. 1. 11. 10:59
반응형

 

 

1931번: 회의실 배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

문제풀이

import sys
input = sys.stdin.readline
n=int(input())
tmp=[]
for _ in range(n):
    tmp.append(list(map(int,input().split())))
#01
tmp.sort(key=lambda x:(x[1],x[0]))
ans,end=0,0
#02
for a,b in tmp:
    if a>=end:
        ans+=1
        end=b
print(ans)

- #01 : 문제에서 주어진 값을 tmp에 입력받고 그 값을 2번째 값을 기준으로 

           오름차순 정렬 후 1번째 값을 기준으로 오름차순 정렬한다.

- #02 : for문을 통해 tmp의 값을 a,b에 대입시킨다.

           만약 a의 값이 end보다 크거나 같다면 회의를 진행할 수 있기에,

           ans에 1을 더해주고, 회의가 끝난 시간인 b를 end에 저장시킨다.

           for문이 끝나고 최종으로 남은 ans를 출력한다.