[Python] 백준 / silver / 1931 (회의실 배정)

문제링크 : https://www.acmicpc.net/problem/1931

그리디 알고리즘 문제이다. silver2 문제이지만, 얻어가는게 많았던 문제이다.
-> 나는 문제를 너무 어렵게 생각하는 경향이 있다,,
회의의 수 1 <= N <= 100,000 이기 때문에,
O(N^2) 미만의 알고리즘을 작성해야한다는 생각은 자연스레 들었다.

우선 N의 회의를 적어도 한 번씩은 처음부터 끝 까지 탐색해야 하므로
O(N)의 시간복잡도는 소요된다. 그 반복문 안에서 O(log N)time 이하의 알고리즘을 적용해야 하는 것이다.

회의는 시작 시간(start)과 끝나는 시간(end)이 주어진다.
어차피 정렬을 하고 그리디 알고리즘을 적용 하는 문제인건 확실한데
어떤 key를 가지고 정렬을 해야할지 꽤 고민되었다.

1. start 로 정렬 -> 반례가 너무 확실했다.
2. end 로 정렬 -> start 정렬 보다는 합리적이었지만 반례가 있었다.
3. "겹치는 회의가 적은 순"으로 정렬 -> 내가 처음 선택한 방법이다.

최대한 많은 회의를 진행해야 하므로 "다른 회의와 겹치는 수가 적은 회의"부터 처리해주면 그리디를 만족한다고 생각했다.
하지만 그게 구현 난이도가 꽤 있었고, 하다보니 시간복잡도가 높았다.

아 이거 어떻게 효율적으로 짜지.. 막 이진탐색도 섞고 dict 자료형도 가져오고 별 난리를 치면서 스스로 문제를 더 어렵게 만들었는데,
그냥 훨씬 쉬운 방법이 있었다. 정렬을 두 번하면 되는 것이었다...

1. 먼저 end로 정렬
2. 그 정렬된 결과에 start로 정렬

회의가 빨리 끝날수록 그 뒤에 할 수 있는 회의가 많아지는건 자명하다. (greedy)
근데 조건에서 "회의는 시작하자마자 끝날 수도 있다"는 조건이 있기 때문에 start로 한번 더 정렬해주면 예외 처리도 할 수 있게된다.
예외 입력 ex)
2
3 3
2 3

정답 코드

import sys
from collections import defaultdict
N = int(sys.stdin.readline())
meetings = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]

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

count = 1
end = meetings[0][1]
for meet in meetings[1:]:
    if meet[0] >= end:
        count += 1
        end = meet[1]

print(count)