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

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

1931번: 회의실 배정

이 문제는 그리디 알고리즘에서

흔히 볼 수 있는 유형이라

꼭 풀어보고 넘어가도록 마음을 먹었습니다.

이 문제는 N개만큼

회의시간이 주어지고

어떻게 회의실을 사용해야

가장 많은 회의를 할 수 있는지가 포인트입니다.

 

우선 그리디알고리즘의 첫 시작.

정렬을 해줍니다.

데이터 안에

[시작,끝]

이렇게 각각을 저장합니다.

그 후에는 

데이터를 정렬합니다.

#백준 1931 회의실 배정

N=int(input())

time=[]
for _ in range(N):
    S,F=map(int,input().split())
    time.append([S,F])

time.sort(key=lambda x:(x[0],x[1]))

이 때 써먹기 좋은 것이

바로 lambda함수입니다.

파이썬의 lambda를 잘 활용하면

복잡한 정렬이 깔끔하게 해결될 수 있습니다.

 

그 다음 강의실을 사용하는 여부입니다.

이전 강의실을 다 쓴 이후에

강의실을 쓸 수 있겠죠?

pre라는, 이전 강의실을 뜻하는 리스트에

[0,0]

(시작,끝)을 넣어줍니다.

이후, time데이터를 돌면서,

회의실을 업데이트 해주면 끝.

#백준 1931 회의실 배정

N=int(input())

time=[]
for _ in range(N):
    S,F=map(int,input().split())
    time.append([S,F])

time.sort(key=lambda x:(x[0],x[1]))

answer=0
#이전 회의 시작+총 회의시간 기록
pre=[0,0]

for t in time:
    if t[0]>=pre[1]:#지금 보는 회의시간이, 이전 화의가 끝난 다음에 이뤄진다면 회의를 진행.
        answer+=1
        pre=t
    elif t[1]<pre[1]:#지금 보는 회의가 끝나는 시간이 이전보다 짧다면, 이걸 쓰는게 맞지. 교체한다.
        pre=t

print(answer)

그리디 알고리즘의 전형적인 문제로

어떻게 시작과 끝만 주어진 데이터들을

최대한으로 고를 수 있는지 생각하게 만든 문제입니다.