[알고리즘] 회의실 배정(그리디)

(문제) 회의실 배정(그리디)

---

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다.

각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

입력설명

첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다.

둘째 줄부터 n+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.

출력설명

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

테스트케이스

입력예제	출력예제
5 1 4 2 3 3 5 4 6 5 7	3
20 18 19 2 20 4 21 2 22 12 15 12 23 2 8 5 20 22 23 1 5 13 21 16 20 9 19 5 9 14 20 16 22 11 12 4 16 21 23 11 13	6

예제설명
(2, 3) , (3, 5), (5, 7)이 회의실을 이용할 수 있다.

---

해결방법

답에 접근하기 위해서는 회의가 끝나는 시간 기준으로 정렬 해야한다.

시작 시간 정렬하면 만약 끝나는 시간이 엄청 늦게 끝나면 정답을 도출할 수 없다.

끝나는 시간을 저장해서 다음 시작 시간과 비교하여 같거나 크면 가능하다.

그러면 밑에 있는 것들도 가능하지 않냐?
밑에 있는게 더 빠를 수 있지 않냐?

하지만 생각을 해보면 우리는 벌써 끝나는 시간으로 정렬하지 않았나!!

이해를 돕기 위해서 예제를 사용하여 한번 해보겠다.

아래와 같이 끝나는 시간 기준으로 정렬 했다!

2 3
1 4
2 5
3 5
4 5
5 7

맨처음 끝나는 시간이 3 이므로 이 3 기준으로 시작하는 시간 3 과 같거나 혹은 큰 것을 찾아야한다.

시작하는 시간 1과 2는 3을 넘지 못하니 버리고, 시작하는 시간 3과 4가 있을 것이다.

둘다 동일한 값이다.
(3, 5)
(4, 5)

이때 필자는 어이없는 생각을 한 적이 있다.
(필자 생각 : 그러면 시작하는 시간 중 4가 3보다 빨리 끝나면요??)

하지만 그럴일이 없다!!

이유는 “이미 우리는 끝나는 시간으로 정렬”을 했기 때문이다.

만약 4가 3 보다 빨리 끝나면 당연히 정렬을 했을 때 4가 3보다 위에 당연히 있을 것이다!!

고로 필자는 빡대가리다 ㅠㅠ 멍청이 … ㅠ

---

코드

# 시작 시간, 끝 시간 최대수 한번 시작하면 중간에 중단 불가능
n = int(input())

arr = [list(map(int,input().split())) for i in range(n)]

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

res = -2174000000
count = 0

for i in range(n):
    if arr[i][0] >= res:
        res = arr[i][1]
        count = count + 1

print(count)