[백준] 9576 책 나눠주기 (파이썬)

문제링크 : https://www.acmicpc.net/problem/9576

문제해결

• 책번호가 a~b 일때, b를 기준으로 정렬해야한다.
• a를 기준으로 정렬 하면 다음과 같은 반례가 생긴다.

3 3
1 2
1 3
2 2 
# 정상 정답 3
# 결과 2

소스코드

import sys

input = sys.stdin.readline

k = int(input())

for _ in range(k):
    n, m = map(int, input().split())

    arr = []

    for _ in range(m):
        arr.append(list(map(int, input().split())))

    book = [i for i in range(1,n+1)]

    arr.sort(key=lambda x:x[1]) # b를 기준으로 정렬
    cnt = 0

    for a, b in arr:
        for i in range(a, b + 1):
            if i in book:
                cnt += 1
                book.remove(i)
                break

    print(cnt)