[Softeer / Level3] 강의실 배정

https://softeer.ai/practice/info.do?idx=1&eid=392 

Softeer

---

그리디 알고리즘의 대표문제이다.

최대한 강의실을 많이 배정하기 위해서 끝나는 시간을 기준으로 하여 정렬하면 된다.

시작, 종료시간을 설정해주고 그다음에 들어오는 튜플의 시작, 종료시간을 재설정 하는식으로 순회시켜준다.

 

 

<내 코드>

import sys

input = sys.stdin.readline
N = int(input())
S = []

for _ in range(N):
    S.append(tuple(map(int, input().split())))

S.sort(key=lambda x: x[1])

p, q, cnt = 0, 0, 0
for start, end in S:
    if p == 0 and q == 0:
        p, q = start, end
        cnt += 1

    if q <= start:
        p, q = start, end
        cnt += 1 

print(cnt)