[백준 1931] 회의실 배정

[BanApp]

import sys

n = int(sys.stdin.readline())
arr = []
for i in range(n):
    arr.append(list(map(int, sys.stdin.readline().split())))
arr.sort(key=lambda x:(x[1],x[0]))

ans = 1
s = arr[0][0]
e = arr[0][1]

for i in range(1,len(arr)):
    if arr[i][0] >= e:
        ans = ans + 1
        e = arr[i][1]

print(ans)

누가봐도 그리디 알고리즘 문제다.
그리디 알고리즘의 문제의 핵심은 정렬이다.
정렬 방식을 잘못하면 답이 나오지 않는다.
잘 생각해보자 정렬 조건은 몇개 안된다.
시작시간이 중요할까? 종료시간이 중요할까?
일찍 끝나는 애들부터 배치하면 그 앞은 신경쓰지 않아도 되는거 아닐까?
만약에 [0,2] 회의와 [3,4] 회의, [4,5] 그리고 [2,5] 회의가 있다고 치자
만약에 시작 시간을 순서로 정렬하면 [0,2]가 들어가고 [2,5] 회의를 넣어보려고 할것이다. 들어가고 더이상 넣을 공간이 없으니깐 답이 2라고 출력할 것이다. 당연히 틀렸다. 이렇듯 시작시간은 중요하지 않다. 중요한건 언제 끝나는지가 중요한거다. 끝나는 시간으로 정렬할 뿐만 아니라 같은 시간에 끝나는 애들은 시작시간이 더 빠른거로 정렬해줘야 한다. 이러한 이유는 [5,5], [5,6], [6,6] 같은 친구들이 있다고 하면 [5,5] 다음에 [6,6] 먼저 넣어버리는 상황을 피하기 위해서다. 그리고 이렇게 생각하는것 말고도 당연히 빈시간 없게 촘촘하게 시간표를 짜야 좋은 프로그램이다.
이렇게 정렬을 해주고 시작시간이 끝시간보다 같거나 크면 ans를 1 더해주고 기준점이 되는 end도 해당 회의의 끝 시간으로 바꿔준다.
ans를 출력해주면 끝~~!