https://www.acmicpc.net/problem/1931
시간 2초, 메모리 128MB
input :
- N(1 ≤ N ≤ 100,000)
- 시작시간 끝나는 시간 (시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0)
output :
- 회의의 최대 개수를 출력
조건 :
- 회의는 한번 시작하면 중간에 중단될 수 없으며
- 회의가 끝나는 것과 동시에 다음 회의가 시작
- 회의의 시작시간과 끝나는 시간이 같을 수도 있다
옛날 어디선가 본거 같은 문제..
회의가 시작하는 시간과 끝나는 시간은 동일 할 수 있다는 것.
그리고, 회의를 어떻게 하면 가장 많이 할 수 있는가.
이는 회의가 끝나는 시간을 오름차순 정렬 해준다. (이를 통해 모든 회의가 어떤 것부터 끝나는지 알 수 있다.)
그리고 정렬해놓은 것을 시작하는 시간 기준으로 오름차순 정렬 해준다. (시작 시간의 정렬로 인해서 아래의 경우에 2가지 경우를 모두 확인 할 수 있다.)
2
2 2
1 2
(2, 2) (1, 2) -> 1가지 경우.
x[0]를 기준으로 오름차순 정렬
(1, 2) (2, 2) -> 2가지 경우.
import sys
n = int(sys.stdin.readline())
data = []
cnt = 0
for i in range(n):
a, b = map(int, sys.stdin.readline().split())
data.append((a, b))
data.sort(key=lambda x : (x[1], x[0]))
now = 0
for start, end in data:
if start >= now:
now = end
cnt += 1
print(cnt)
