* 백준 1931번 - 회의실 배정

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

# 틀린코드

틀린코드라고 할 것도 없다. 문제를 해결할 수 있는 아이디어를 떠올리지 못했다. 가능한 회의의 최대 개수를 찾기 위해 두가지를 떠올렸다.
첫번째로 회의시간이 짧은 것을 우선으로 배치하면 되지 않을까? 이 생각을 반박하는 생각이 그 뒤에 바로 들었다. 회의시간이 짧아도 회의끼리 텀이 길면 최대 개수가 아닐 수 있다. 아닐 수 있다는 건 일반화가 안되었다는 것. 즉, 예외가 있기 때문에 문제를 해결할 수 없다.
두번째는 회의시간이 빠른 순서대로 배치한다. 빨리 시작하면 많은 회의를 넣을 수 있지 않을까? 근데 빨리 시작한다고 짧은 회의가 아니다. 이걸 하나하나 어떻게 다 비교하지? 예외케이스가 너무 많아진다.
정답을 듣고나면 이걸 왜 못 생각해냈는지 모르겠을 정도로 당연하다. 정답은 빨리 끝나는 회의를 우선적으로 선택하면 된다. why? 회의가 빨리끝나면 그만큼 회의실을 쓸 수 있는 시간이 많아진다. 쓸 수 있는 시간이 더 적은데 더 많은 회의를 할 수 있는 방법은 없다. 그러므로 타당한 이론이다.

# 정답코드

회의 종료시각을 기준으로 정렬하는데, 종료시각이 같은 경우 시작시각의 오름차순으로 정렬한다. 그 이유는 문제에서 주어진 시작시각과 종료시각이 같은 회의가 존재하기 때문이다. (2,2)가 먼저 오게 되면 (1,2) 회의를 못한다고 처리하지만 (1,2) 회의 뒤에는 (2,2) 회의가 가능하다.
다음 회의의 시작시각이 이전 회의의 종료시각보다 늦거나(크면) 같으면 회의를 할 수 있다고 판단하여 카운트한다.

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
conferences = deque()
for _ in range(N):
  a, b = map(int, input().split())
  conferences.append((a, b))

fastEndConf = deque(sorted(conferences, key=lambda x:(x[1],x[0])))
shortConf = fastEndConf.popleft()
count = 1
while fastEndConf:
  if shortConf[1] > fastEndConf[0][0]:
    fastEndConf.popleft()
  else:
    shortConf = fastEndConf.popleft()      
    count += 1
    
print(count)