정답 비율: 29.358%
문제 풀이
시간이 2초나 주어져서 greedy 방식으로 문제를 풀어야 하는 건가 싶었다.
먼저 시작 시간이 빠른 순서대로 정렬을 한다. 그 다음으로 빨리 끝나는 회의 순서대로 정렬을 해야 한다. 빨리 끝날수록 뒤에서 고려해볼 회의가 많기 때문이다. 빨리 시작하는 순서대로 정렬을 우선 한다면 오히려 늦게 끝날 수 있다.
예를 들어 회의 시간이 [4,6], [2,12], [3,4], [1,2], [2,3] 이렇게 주어질 때, 시작 시간으로 정렬하면 [2,12]로 1번의 회의가 가능하지만 끝나는 시간으로 정렬하면 총 3번의 회의가 가능해진다. [1,2] ,[2,3], [3,4], [4,6], [2,12]
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 회의 수 n 입력받기
n = int(input())
# 각 회의 시작 시간, 끝나는 시간 입력받기
times = []
for _ in range(n):
times.append(list(map(int, input().split())))
times.sort(key=lambda x: x[0]) # 시작 시간 기준으로 정렬
times.sort(key=lambda x: x[1]) # 끝나는 시간 기준으로 정렬
# times.sort(key=lambda x: (x[1], x[0]))
cnt = 0
last = 0
for start, end in times:
if start >= last:
cnt += 1
last = end
print(cnt)