그리디

---

문제 035 회의실 배정하기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	189495	60855	42429	30.055%

문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

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

예제 출력 1
4

---

sort()를 이용한 기본적인 그리디 문제이다. 회의를 가장 많이 진행하기 위해선 회의가 끝나는 시간이 중요하다. 결국 회의가 끝나는 시간이 빨라야 그 다음 팀이 빠르게 들어올 수 있기 때문이다. 따라서 정렬을 회의가 끝나는 순으로 정렬해야 한다. 람다식을 사용하여 정렬의 기준을 설정할 수 있다. 다음 코드를 확인하자.

import sys
sys.stdin = open('input.txt', 'rt')

n = int(input())
t = []
cnt = 0
tmp = 0

for _ in range(n):
    s, e = map(int, input().split())
    t.append((s, e))
t.sort(key=lambda x: (x[1], x[0]))

for i in range(n):
    if tmp <= t[i][0]:
        tmp = t[i][1]
        cnt += 1

print(cnt)

코드를 보면 람다식을 사용하여 끝나는 순으로 정렬되도록 하였다. 물론 sort()의 default는 가장 앞에 있는 값을 기준으로 정렬하기 때문에 e를 맨 앞에 저장함으로써 람다식을 쓰지 않을 수도 있지만 람다는 종종 유용하게 쓰이므로 연습 차원에서 람다를 사용했다. 추가적으로, 첫 번째 값을 기준으로 정렬을 마친 후 두 번째 기준을 적용하고 싶을 때가 있다. 이 문제도 마찬가지로 두 번째 기준을 적용해야 한다. 그럴 땐 람다식에 위와 같이 추가해주면 된다. (종료 시간이 같으면 시작 시간이 빠른 순서로 정렬하는 로직도 추가해야 함.)