1931 회의실배정 [그리디 알고리즘]

그리디 알고리즘 탐욕법으로 가장최적인 답을 선택하는 패러다임을 이용하면 된다 [이 용어에 대해서는 아직 잘 모르겠다]

input이 최대 100000번이 될수도 있으니 input함수대신 sys.stdin 을 이용하구

정렬되는데 걸리는시간이 O(NlgN) 에다 반복문 2번 2N이므로  이므로 대략 시간복잡도는 O(NlgN) 으로 풀수가 있다.

회의가 끝나는 시간을 기준으로 정렬하고

다시 반복문을 통해 회의가 제일 일찍 끝나는시간을 y_min 저장한후 회의시작시간이 y_min 보다 더 높은값이 나오면 

그에 따른 회의시간이 끝나는 기준을 y_min에 저장 cnt 증가 반복을 통해 풀수 있다.

import sys
read = sys.stdin.readline

n = int(read())
arr = []
for i in range(n):
    a, b = map(int, read().split())
    arr.append((b, a))

arr.sort()

y_min, cnt = 0, 0
for b, a in arr:
    if a >= y_min:
        y_min = b
        cnt += 1

print(cnt)