[백준] 1931번 : 회의실 배정

유형 : 정렬, 그리디

1. 문제

 

예제

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

 

예제 출력

4 # (1,4), (5,7), (8,11), (12,14)

---

2. 코드

N = int(input())
data = []
for _ in range(N):
    data.append(list(map(int, input().split())))

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

cnt = 1
x = data[0][1] # 끝
for i in range(1,N): # 첫 번째 회의를 두 번째 회의 일정부터 비교
    if x <= data[i][0]: # 시작(data[i][0])과 끝을 비교
        cnt += 1        # 다음 시작이 끝보다 크거나 같으면 다음 회의로 넘어갈 수 있음
        x = data[i][1] # 끝

print(cnt)

 

여기서 핵심은 정렬이다. (x,y)라고 했을 때 y를 기준으로 정렬한 뒤 x를 기준으로 정렬을 한다.(둘 다 오름차순으로) 현재 위치에서 끝값과 그 다음 회의의 처음 값을 비교하는데, 정렬을 통해 둘의 차이가 작으면서 회의가 많이 진행되도록 할 수 있다. (말이 횡설수설한 것 같다)

⇒ 주어진 시작시간과 끝나는 시간들을 이용해서 가장 많은 회의의 수를 알기 위해서는 빨리 끝나는 회의 순서대로 정렬을 해야 한다. 빨리 끝날수록 뒤에서 고려해볼 회의가 많기 때문이다. 
출처: https://suri78.tistory.com/26 [공부노트]

 

참고로 예시를 정렬했을 경우 아래와 같다.

[[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]

 

참고 : https://suri78.tistory.com/26

문제 출처 : https://www.acmicpc.net/problem/1931