[Gold II] 책 나눠주기 - 9576 (그리디)

[Gold II] 책 나눠주기 - 9576

백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다.

조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다.

백준이가 책을 줄 수 있는 최대 학생 수를 구하시오.

입력

첫째 줄에 테스트 케이스의 수가 주어진다.

각 케이스의 첫 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 줄부터 M개의 줄에는 각각 정수 ai, bi가 주어진다. (1 ≤ ai ≤ bi ≤ N)

출력

각 테스트 케이스마다 백준이가 책을 줄 수 있는 최대 학생 수를 한 줄에 하나씩 출력한다.

* 접근 방법
보자마자 쉽게 그리디적인 방법이 생각났다. ( 조금 난이도 있는 골드 2 문제여서 긴가민가했다. )
그러나, 책 번호를 오름차순으로 정렬하고 맨 앞 번호부터 차례대로 방문 체크하면 될 줄 알았지만, 반례가 있었다.
반례)
```
3
1 3
2 3
2 4
3 3
answer = 4
출력 = 3
```
* 풀이 방법
그러므로, 반례를 토대로 내림차순으로 정렬하여 맨 뒤 번호부터 차례대로 방문 체크하면 해결되었다.
아마도 스터디원 분들께서 반례를 던져주지 않았다면 푸는데 훨씬 더 오래 걸렸을 것이다. 어쩌면 테스트 케이스가 부족해서 골드2 일수도 있겠다는 생각이 들었다.

for i in range(int(input())):
  n, m = map(int,input().split())
  books = []
  visited = [0] * (n+1)

  for i in range(m):
    books.append(list(map(int,input().split())))

  books.sort(reverse=True)

  for i in books:
      for j in range(i[1], i[0]-1, -1):
          if not visited[j]:
              visited[j] = 1
              break
          
  print(visited.count(1))