λ¬Έμ
μκ°μ μ²μ λ§μ€ν° κΉμ’ ν μ μλμκ² μλ‘μ΄ κ³Όμ κ° μ£Όμ΄μ‘λ€.
κΉμ’ ν μ μλνν λ Siμ μμν΄μ Tiμ λλλ Nκ°μ μμ μ΄ μ£Όμ΄μ§λλ°, μ΅μμ κ°μμ€μ μ¬μ©ν΄μ λͺ¨λ μμ μ κ°λ₯νκ² ν΄μΌ νλ€.
μ°Έκ³ λ‘, μμ μ΄ λλ μ§νμ λ€μ μμ μ μμν μ μλ€. (μ¦, Ti ≤ Sj μΌ κ²½μ° i μμ κ³Ό j μμ μ κ°μ΄ λ€μ μ μλ€.)
μκ°μ μ² λμΆ©ν κ² μ°λ¦¬λ©΄, μ μλμ λμλ리μ!
μ λ ₯
첫 λ²μ§Έ μ€μ Nμ΄ μ£Όμ΄μ§λ€. (1 ≤ N ≤ 200,000)
μ΄ν Nκ°μ μ€μ Si, Tiκ° μ£Όμ΄μ§λ€. (1 ≤ Si < Ti ≤ 109)
μΆλ ₯
κ°μμ€μ κ°μλ₯Ό μΆλ ₯νλΌ.
μ μ νμ΄λ΄€λ 그리λ μκ³ λ¦¬μ¦μ΄λ λ¬λΌμ κ³μ ν΅κ³Ό λͺ»νκ³ μλ€κ° λ΄κ° λ¬Έμ λ₯Ό μλͺ»μ΄ν΄νλ€λκ±Έ κΉ¨λ¬μλ€...
κ·Έ μ μ νμλ λ¬Έμ λ μ΅λν λ§μ μμ μ λ€μ μ μλ λ°©λ² or ν κ°μμ€μμ μ΅λμ κ°μμ μ΄λ°κ±Έλ‘ νμμ΄μ λλλ μκ°μ΄ κ°μ₯ λΉ λ₯Έ μμλλ‘ μ λ ¬ν΄μ λ€μ μμμκ°κ³Ό λΉκ΅νλ λ°©λ²μ΄μλλ°, μ΄κ±΄ κ·Έ λ°λμλ...π νμ°Έμ ν€λ§Έλ€!!
β λ¬Έμ μ΄ν΄
- λͺ¨λ μμ μ λ€μ΄μΌνλ€.
- λͺ¨λ μμ μ λ£κΈ° μν΄μ νμν κ°μ₯ μ΅μμ κ°μμ€ μλ?
μμ λ₯Ό κ·Έλ¦ΌμΌλ‘ λνλΈλ€λ©΄,
κ°μ μμΌλ‘ λ κ°μκ° κ°μ κ°μμ€μ μ΄λ€λ κ²μ΄λ€.
κ·Έλμ μ΄ 2κ°μ κ°μμ€μ΄ νμνλ€.
β λ¬Έμ νμ΄
κ°μ μμ 리μ€νΈμ μ’ λ£ λ¦¬μ€νΈλ₯Ό 2μ°¨μ 리μ€νΈλ‘ λ¬Άκ³ , μμ μκ°μ κΈ°μ€μΌλ‘ μ€λ¦μ°¨μμΌλ‘ μ λ ¬νλ€.
heapqλ₯Ό μ¬μ©νλ©΄ 리μ€νΈκ° νμ μ€λ¦μ°¨μμΌλ‘ μ λ ¬μ΄ λλ€.
κ°μλ λͺ¨λ λ€μ΄μΌ νκΈ° λλ¬Έμ μ²μ μμνλ κ°μμ λλλ μκ°μ heapqμ λ£κ³ , q리μ€νΈμ μ΅μκ°κ³Ό λ€μ μμ μ μμμκ°μ λΉκ΅νλ€.
λ§μ½ λ€μ κ°μ μμ μκ°μ΄ 리μ€νΈμ μ΅μκ°λ³΄λ€ ν° κ°μ΄λΌλ©΄ μ΅μκ°μ μμ νλ€.
λ€μ κ°μμ λλλ μκ°μ q리μ€νΈμ λ£λλ€.
λ§μ§λ§μΌλ‘ q리μ€νΈμ κΈΈμ΄λ₯Ό μΆλ ₯νλ©΄ μ΄ κ°μμ€ μκ° λμ¨λ€!
π μ½λ
import heapq
import sys
def greedy_lecture_num(list):
q = []
heapq.heappush(q,list[0][1])
for i in range(1, len(list)):
if q[0] <= list[i][0]:
heapq.heappop(q)
heapq.heappush(q, list[i][1])
return len(q)
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])
print(greedy_lecture_num(list))
python μ½λλ‘ μ μΆν λ input()ν¨μ μ¬μ©νλ©΄ μλκ² λ€γ γ μκΎΈ νμμμμ΄λ€..
μμΌλ‘ κΌ sys.stdin.readline() μ¬μ©ν΄μΌμ§!!