[백준] 그리디 알고리즘 - 회의실 배정

[문제]

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

1931번: 회의실 배정

[어떻게 풀까?]

이 문제는 백준에 나와있는 예시 자체가 힌트였다. 어떻게 풀까 고민하던 중에 먼저 눈치 챈 것은 끝나는 시간이 작을 수록 좋다는 것이다. 회의가 빨리 끝나야 다음회의를 할 수 있고, 애초에 끝나는 시간보다 시작하는 시간이 더 빠르니까 말이다. 이것을 고려하여 수를 정렬해주면 되는데 어떻게 정렬할지 몰라서 

https://dailyheumsi.tistory.com/67

파이썬 정렬, 다중 조건으로 한 번에 하기.

이분의 블로그를 참고하였다. sorted와 lambda를 섞어서 쓰면 되는데 정말 정리가 잘 되어 있어서 나중에 나도 봐야겠다. 아무튼 이런식으로

이런식으로 정리가 되고 나면 그 다음은 쉽다. 왜냐하면 숫자가 안 겹치게 세기만 하면 되기 때문이다. 

[코드]

n = int(input())

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

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


for i in range(n):
    if array[i][0] >= NextTime:
        result += 1
        NextTime = array[i][1]

print(result)