백준 1931번 회의실 배정

문제 파악

1. 회의의 수 N(1 ≤ N ≤ 100,000), 시간제한 2초:약 4*10^7 -> O(N^2) 불가능
2. 예제입력에서 회의 끝나는 시간은 정렬되어 있는 것처럼 보인다.

예제입력 1
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

3. 2번에서 힌트를 얻었다. 끝나는 시간이 빠른 것부터 쌓아나가야 최대한 많은 회의를 할 수 있다.

코드

from sys import stdin

input = stdin.readline
ans = 0
n = int(input())
meeting = []
for _ in range(n):
    tmp = tuple(map(int, input().split()))
    meeting.append(tmp)
meeting.sort(key=lambda x: (x[1], x[0]))
latest = 0
for m in meeting:
    if m[0] >= latest:
        latest = m[1]
        ans += 1
print(ans)

• meeting 리스트에 각 튜플 (회의시작, 회의종료)이 저장된다.
• 종료시간을 기준으로 정렬, 같으면 시작시간을 기준으로 정렬

TIL

.sort()에서 정렬 기준을 설정하는 법

일반적인 패턴은 객체의 인덱스 중 일부를 키로 사용하여 복잡한 객체를 정렬하는 것입니다. 예를 들어:

student_tuples = [
    ('john', 'A', 15),
    ('jane', 'B', 12),
    ('dave', 'B', 10),
]
sorted(student_tuples, key=lambda student: student[2])   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

처음 문제를 풀 때 회의 종료시간만 기준으로 정렬했다가
(3,3), (1,3) 같은 입력을 처리하지 못했다.
sort()에서 정렬 조건을 두개 주는 방법을 까먹었었다.