https://www.acmicpc.net/problem/11062
시간 1초, 메모리 256MB

input :

• 테스트케이스의 수 T
• N M(1 ≤ N, M ≤ 1,000)
• ai, bi가 주어진다. (1 ≤ ai ≤ bi ≤ N)

output :

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

조건 :

• 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다.

• 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다.

---

우선 문제의 형태가 너무 이분매칭이랑 비슷하게 생겼다. 그래서 학생을 목표로 두고 책에 대해서 이분 매칭을 수행하게 하였는데 이 경우 시간 초과가 발생한다.

그래서, 다른 접근으로 그리디적인 문제로 접근할 수 있다. 회의실 배정과 같이 b에 대해서 정렬을 한 후에 나눠준다면? 해결이 가능하다.

다음 풀이

1. 특정 인원에게 1권을 제공?
2. a ~ b까지의 책 범위

이분 매칭이 되지 않는 근거가 필요할 듯. dfs를 지속적으로 하는 것을 계산하면 되지 않을까.
그리디적으로 접근할 시에 더 빠르게 해결이 가능. 그러나, 범위로 정렬을 하게 된다면 의도하지 않는 결과를 얻을 수 있다.

1
3 3
1 2
2 3
3 4
1 3
과 같은 예시에서 1 3 이 2로 범위가 제일 커서 뒤에 둔다면, 3을 출력하지만 b를 기준으로 정렬한다면 4를 출력하게 된다. 그래서 b를 기준으로 정렬해야 한다.

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n, m = map(int, sys.stdin.readline().split())
    book, data = [0] * (n + 1), []

    for i in range(1, m + 1):
        a, b = map(int, sys.stdin.readline().split())
        data.append((a, b))

    data.sort(key=lambda x:x[1])
    for a, b in data:

        for i in range(a, b + 1):
            if book[i] == 0:
                book[i] = 1
                break

    print(sum(book))