문제
백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다.
조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다.
백준이가 책을 줄 수 있는 최대 학생 수를 구하시오.
입력
첫째 줄에 테스트 케이스의 수가 주어진다.
각 케이스의 첫 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 줄부터 M개의 줄에는 각각 정수 ai, bi가 주어진다. (1 ≤ ai ≤ bi ≤ N)
출력
각 테스트 케이스마다 백준이가 책을 줄 수 있는 최대 학생 수를 한 줄에 하나씩 출력한다.
예제 입력 1
1
2 3
1 2
1 2
1 2예제 출력 1
2나의 풀이
필자는 a와 b중 b를 기준으로 오름차순 정렬을 한 뒤 그리디하게 문제를 해결할 수 있었다. 처음에 a를 기준으로 먼저 정렬한 뒤 같다면 b를 기준으로 오름차순 정렬을 하여 코드를 작성하였더니 자꾸 50%에서 틀렸다... 그래서 반례를 찾아보니 아래와 같은 반례에서는 처음 작성하였던 코드로는 2가 나왔다,...
3 3 1 2 1 3 2 2 // 3이 정상 정답이러한 반례를 찾고나니 왜 b를 기준으로 정렬을 해야하는지 이해가 갔다.
정렬을 한 뒤에는 a부터 b까지 방문하진 않은 book을 체크하고 카운터를 증가시키면 된다.
코드
# 9576번 책 나눠주기
from collections import deque
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
books = [False] * (n+1)
requests = []
for _ in range(m):
requests.append(list(map(int, input().split())))
requests.sort(key=lambda x: x[1])
cnt = 0
while requests:
a, b = requests.pop(0)
for i in range(a, b+1):
if not books[i]:
cnt += 1
books[i] = True
break
print(cnt)
