[Python] 백준 9576: 책 나눠주기

https://www.acmicpc.net/problem/9576

9576번: 책 나눠주기

1. scope의 scope[1]을 기준으로 정렬한다. 책의 앞번호부터 나눠주기 위함이다. (만약 뒤에서부터 나누어주면 7 8

8 8  이런식으로 값이 들어오면 ans 는 1이된다. 이것때문에 틀렸다.)

2. find 함수로 책을 나눠줬으면 다음 인덱스의 책으로 이동한다.

3. 책을 나누어줄 범위를 벗어나면  ans값을 올리지 않는다.

T = int(input())

def find(x):
    if x > b:
        return -1
    if x == unf[x]:
        unf[x] += 1
        return x
    else:
        tmp = find(unf[x])
        if tmp != -1:
            unf[x] = tmp
            return unf[x]
        else:
            return -1

while T:
    T -= 1
    ans = 0
    n, m = map(int, input().split())
    unf = [i for i in range(n+1)]
    scope = [list(map(int, input().split())) for _ in range(m)]
    scope.sort(key=lambda x: (x[1]))
    for a, b in scope:
        if find(a) != -1:
            ans += 1
    print(ans)