이번 문제는 그리디 알고리즘을 통해 쉽게 해결하였다. 서류들의 정렬이 중요했다. 처음에는 a, b-a의 오름차순으로 정렬하고, 책 리스트를 만들어 선택될 때 체크하는 과정을 반복하였다. 예제는 잘 맞았지만, 50%에서 오답처리를 받았다. 그래서 50%에 대한 테스트 케이스를 찾아보았다.

input: 1
	   3 3
       1 2
       1 3
       2 2
output: 2
answer: 3

위의 테스트케이스를 내 풀이대로 정렬하면 (1, 2), (1, 3), (2, 2)로 정렬된다. 그러면 (1, 2)에서 1번 책을, (1, 3)에서 2번 책을 받기 때문에 (2, 2)는 책을 받을 수 없게 된다. 그래서 정렬 우선순위를 a, b-a에서 b, b-a로 변경하였다. 이렇게 하면 다음과 같이 정렬되고 풀이된다.

(2, 2), (1, 2), (1, 3) -> (2, 2): 2번 책, (1, 2): 1번 책, (1, 3): 3번 책

이러한 방식으로 정렬하여 답을 구하였다.

Code

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    doc = [list(map(int, input().split())) for _ in range(m)]
    books = [False for _ in range(n+1)]
    doc.sort(key= lambda x:(x[1], x[1]-x[0]))
    for i in range(m):
        for j in range(doc[i][0], doc[i][1]+1):
            if books[j]:
                continue
            books[j] = True
            break
    print(books.count(True))