λ¬Έμ
ν κ°μ νμμ€μ΄ μλλ° μ΄λ₯Ό μ¬μ©νκ³ μ νλ Nκ°μ νμμ λνμ¬ νμμ€ μ¬μ©νλ₯Ό λ§λ€λ €κ³ νλ€. κ° νμ Iμ λν΄ μμμκ°κ³Ό λλλ μκ°μ΄ μ£Όμ΄μ Έ μκ³ , κ° νμκ° κ²ΉμΉμ§ μκ² νλ©΄μ νμμ€μ μ¬μ©ν μ μλ νμμ μ΅λ κ°μλ₯Ό μ°Ύμ보μ. λ¨, νμλ νλ² μμνλ©΄ μ€κ°μ μ€λ¨λ μ μμΌλ©° ν νμκ° λλλ κ²κ³Ό λμμ λ€μ νμκ° μμλ μ μλ€. νμμ μμμκ°κ³Ό λλλ μκ°μ΄ κ°μ μλ μλ€. μ΄ κ²½μ°μλ μμνμλ§μ λλλ κ²μΌλ‘ μκ°νλ©΄ λλ€.
μ λ ₯
첫째 μ€μ νμμ μ N(1 ≤ N ≤ 100,000)μ΄ μ£Όμ΄μ§λ€. λμ§Έ μ€λΆν° N+1 μ€κΉμ§ κ° νμμ μ λ³΄κ° μ£Όμ΄μ§λλ° μ΄κ²μ 곡백μ μ¬μ΄μ λκ³ νμμ μμμκ°κ³Ό λλλ μκ°μ΄ μ£Όμ΄μ§λ€. μμ μκ°κ³Ό λλλ μκ°μ 231-1λ³΄λ€ μκ±°λ κ°μ μμ°μ λλ 0μ΄λ€.
μΆλ ₯
첫째 μ€μ μ΅λ μ¬μ©ν μ μλ νμμ μ΅λ κ°μλ₯Ό μΆλ ₯νλ€.
β μμ μ€λͺ
λͺ¨λ νμ μΌμ μ μ μΌλ‘ λνλΌ λ, ν νμμ€μμ κ°μ₯ λ§μ νμλ₯Ό ν μ μλ μ΅λκ°μ 4μ΄λ€.
β νμ΄λ°©λ²
greedy μκ³ λ¦¬μ¦μ μ¬μ©νλ€.
κ°μ₯ λ§μ νμλ₯Ό ν μ μλ λ°©λ²μ κ°μ₯ 빨리 λλλ νμλ€μ μ ννλ λ°©λ²μ΄λ€.
λ°λΌμ νμκ° λλλ μκ°μ μ€λ¦μ°¨μμΌλ‘ μ λ ¬νκ³ , λ€μμΌλ‘ λλλ νμμ μμμκ°κ³Ό μ μ λλ¬λ νμμ λλλ μκ°μ λΉκ΅νμ λ μμ μκ°μ΄ λλλ μκ°κ³Ό κ°κ±°λ ν¬λ©΄ countλ₯Ό 1μ¬λ¦¬λ©΄ λλ€.
β λλλ μκ°μ μ€λ¦μ°¨μμΌλ‘ μ λ ¬νλλ°, λλλ μκ°μ κ°μλ° μμ μκ°μ΄ λ€λ₯Έ κ²½μ°μ λΉκ΅κ° μ μλ μλ μ λ€!! κ·Έλμ κΌ κΌ μμμκ°μ λ¨Όμ μ λ ¬νλ€μμ λλλ μκ°μ μ€λ¦μ°¨μμΌλ‘ ν λ² λ ν΄μ€λ€. κ·ΈλΌ λλλ μκ°μ΄ λμΌν΄λ λ¨Όμ μμνλ νμκ° μμ μμΉνλ€.
π μ½λ
import sys
def greedy_meeting_room(list):
k = 0
count = 1
for i in range(1, len(list)):
if list[k][1] <= list[i][0]:
count += 1
k = i
return count
N = int(sys.stdin.readline())
list = [[0 for j in range(2)] for i in range(N)]
for i in range(N):
start, finish = map(int, sys.stdin.readline().split())
list[i][0], list[i][1] = start, finish
list.sort(key = lambda x : x[0]) # μμμκ° μ λ ¬
list.sort(key = lambda x : x[1]) # λλλ μκ° μ λ ¬
print(greedy_meeting_room(list))