책 나눠주기

🤔 접근

처음에는 이분탐색 문제라고 확신하고 풀었지만 시간초과를 받았다. 그래서 다시 문제를 읽고 생각해보니, 원하는 책이 범위로 주워졌다는 점에서 이분탐색이 아닌 그리디로도 충분히 해결 가능하다고 생각했다.

몇 번의 테스트케이스를 돌려본 후, 감이 왔다. n이 작은 책부터 나눠준다고 생각하면, 가장 책을 급하게 받아야 하는 사람은 b가 작은 사람일 것이다. 만약 b가 같다면, a가 큰 사람한테 책을 우선적으로 줘야 한다고 생각했다.

💻 코드

# 9576
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    table = []
    for _ in range(m):
        a, b = map(int, input().split())
        table.append([a, b])

    table.sort(key = lambda x : (x[1], -x[0]))

    taken = [0] * (n + 1)
    cnt = 0
    for p in table:
        for book in range(p[0], p[1]+1):
            if not taken[book]:
                taken[book] = 1
                cnt += 1
                break
    print(cnt)