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

www.acmicpc.net/problem/1931

1931번: 회의실 배정

문제 설명

한 개의 회의실에서 N개의 회의가 이루어진다.

각각의 회의 I에 대해 시작시간과 끝나는 시간이 주어지며, 각 회의실은 겹쳐서 사용할 수 없다.

단, 끝나는 즉시 다음 회의가 시작을 이어받을 수 있으며, 시작 시간과 끝나는 시간이 같을 수도 있다.( 시작 즉시 종료 )

이 때, 열릴 수 있는 회의의 최대 갯수를 구하면 된다.

---

풀이 과정

대표적인 그리디 개념을 이용하는 문제이다.

그리디는 당장의 상황을 기준으로 확장시키는 방향으로 풀면 쉽게 해결이 가능한 경우가 많다.

내가 회의실을 사용하고 있다고 가정했을 때, 내 회의가 끝난 후에 회의실에서 가장 많은 회의가 열리기 위해서는 어떤 상황이 되야할까? 바로. 내 회의가 빨리 끝나야 하는 것이다. 즉, 종료 시간이 빨라야 한다.

여기서 한가지 더 고려해야 할 점은 바로 종료시간이 같은 경우이다.

예를 들어, (10, 10) 의 회의와 (9,10)회의가 있을 때, 둘의 종료 시간은 같지만, (9,10)를 먼저 선택하면, (10,10)의 회의를 선택할 기회가 주어진다. 하지만, (10, 10)의 회의가 먼저 선택되면, 종료시간이 10을 넘어갔기 때문에 9시작은 고려되지 않는다.

따라서 시작시간으로 먼저 정렬을 해준 후에, 종료 시간을 기준으로 정렬을 해준다.

 

이렇게 정렬을 한 후에, 종료 시간을 꼬리잡기 식으로 이어나가면 최대 개수를 구할 수 있게 된다.

n = int(input())
room = []

for i in range(n):
    a, b = map(int, input().split())
    room.append([a, b])

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

cnt = 1
end = room[0][1]
for i in range(1, n):
    if room[i][0] >= end:
        cnt += 1
        end = room[i][1]

print(cnt)

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !