풀이
-
우리는 회의를 최대한 많이 하도록 해야 하므로 회의의 끝나는 시간이 빠를 수록 좋다.
그래서 먼저 회의가 끝나는 시간을 시간순 즉 오름차순으로 정렬한다.
그리고 모든 회의 시간을 돌면서 다음 회의의 시작하는 시간이 전 회의의 끝나는 시간보다 같거나 크면 count해주면 된다. -
그런데 여기서 중요한 것! 문제에서 다음과 같이 말했다.
회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
그래서 회의가 시작되는 시간도 오름차순으로 정렬해야 한다.
안 그러면 다음과 같은 input이 주어졌다면
2 2
1 2
회의실을 1번만 사용 가능하게 되버리는데, 원래는 1시부터 2시까지 하고 2시 시작하자마자 끝나는 회의까지 총 2번 가능하다.
코드
import sys
input = sys.stdin.readline
N = int(input())
time = []
for _ in range(N):
a, b = map(int, input().split())
time.append((a, b))
time.sort(key=lambda x : (x[1], x[0]))
end = 0
cnt = 0
for i in time:
if end <= i[0]:
end = i[1]
cnt += 1
print(cnt)-
힌트에서
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
라고 해서 회의 시간과 끝나는 시간을 튜플로 리스트에 저장했다.
-
그리고 오름차순으로 두 번 정렬하는 것은 전에 많이 해봤던 것처럼 lambda를 이용했고, 문제에 맞춰 끝나는 시간으로 먼저 정렬이 되도록 했다.
결과
