https://www.acmicpc.net/problem/11062
1秒、256 MBメモリ
input :

試験盤ケース数T

N M(1 ≤ N, M ≤ 1,000)

ai,bi.(1 ≤ ai ≤ bi ≤ N)

output :

個のテストケースごとに、行ごとに柏俊が本を与えることができる最大学生数

を出力します.
条件:

本を区別するために、それぞれ1からNまでの整数番号を重複しないようにします.

本番号a以上b以下の本の中から残りの本を選んでその学生にあげます.

まず問題の形態はこの組み合わせとよく似ている.そのため、学生を目指して本を二分マッチングする場合、タイムアウトが発生します.
だから、別の方法でギリシャ式の問題に近づくことができます.会議室が手配して、bを並べ替えてから配布したら?解決できる.

次の解

特定の人に本を提供しますか?

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))