[백준] 1931번 회의실 배정

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

array = sorted(array, key = lambda x: x[0])
array = sorted(array, key = lambda x: x[1])

count = 1
i = 1
k = 0
while i < len(array):
    if array[k][1] <= array[i][0]:
        k = i
        count = count + 1
    i = i + 1
print(count)

이런 그리디 알고리즘은 처음이라 푸는 방법을 찾아보며 풀었다.

정렬을 2번 해줘야 한다.

1. 끝나는 시간이 빠른 순

2. 끝나는 시간이 같다면, 시작하는 시간이 빠른 순

 

이 두가지의 정렬을 위해서는

1. 시작하는 시간 순서대로 정렬

2. 끝나는 시간 순서대로 정렬

이 순서대로 정렬을 해줘야 원하는 순서를 얻을 수 있다.

시작하는 시간을 순서대로 정렬을 하고 난 후 끝나는 시간 순서대로 정렬을 하고 나면, 끝나는 시간이 같은 경우에는 시작하는 시간이 빠른 순서대로 정렬이 된다.