9576. 책 나눠주기

오늘 코테를 봤는데 짧은 시간안에 문제를 더많이 풀려면 구현실력을 더 길러야 겠다는 생각을 했다..!!

째튼.. 이 책나눠주기 문제는 그리디 문제이다.

 

문제에서 주어진 a와 b의 범위중 b를 기준으로 정렬해야한다. -> 끝에가 가장 작은거 부터. 왜냐? 어짜피 a<= b 니까.

정렬 후 앞에 원소를 빼주면서 방문 안했으면 방문시킨다.

import sys
input = sys.stdin.readline
for _ in range(int(input())):  
  n,m =map(int,input().split())
  books = [False] * (n+1)
  r = [list(map(int,input().split())) for _ in range(m)]
  r.sort(key = lambda x : x[1])
  cnt = 0 
  while r: 
    a, b = r.pop(0)
    for i in range(a, b+1):
      if not books[i]:
        cnt += 1
        books[i] = True
        break
  print(cnt)

끗