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

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

문제해결 아이디어

• 그리디문제이고, 정렬조건을 잘 정하면 맞출 수 있는 문제였다.
• 결과적으로 수령하려는 책의 뒷번호가 작은 순서로 정렬하고
• 앞 번호의 책부터 수령하면 해결되는 문제였다.

소스코드

import sys
input = sys.stdin.readline
# 책의 번호가 큰 순서로 정렬해서 큰 책부터 전달하는 경우
# (1,3),(1,3),(2,2) 에서 안됨
# 책의 번호가 작은 순서대로 정렬해서 큰 책부터 전달하는 경우
# (1,2),(2,3),(2,2) 에서 안됨

# 책의 번호가 작은 순서대로 정렬해서 작은 책부터 전달
for _ in range(int(input())):
    cnt = 0
    n, m = map(int, input().split())
    arr = []
    for _ in range(m):
        arr.append(list(map(int, input().split())))

    arr.sort(key=lambda x: x[1])

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

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

    print(cnt)