[python] 백준 9576 책 나눠주기

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

9576번: 책 나눠주기

 

문제 해결

• 어떤 범위를 가진 학생한테 먼저 책을 줄지 생각을 해야한다.
• 범위길이가 작은 사람부터 해결하는 것이 좋다.(가능한 경우의 수가 적으므로)
• 그러면 right upperbound는 작을수록, left lowerbound는 클 수록 먼저 해결하는 것이 좋다.

 

 

CODE

from collections import deque

for _ in range(int(input())):
    n, m = map(int ,input().split())
    books = [False]*(n+1)
    r = []
    for _ in range(m):
        a, b = map(int, input().split())
        r.append((a,b))
    r.sort(key= lambda x: (x[1],-x[0]))
    cnt = 0
    while r:
        a, b = r.pop(0)
        for i in range(a,b+1):
            if not books[i]:
                cnt += 1
                books[i] = True
                break
    print(cnt)