BOJ 9576: 책 나눠주기 [Python 3]

오늘의 문제는 책 나눠주기라는 문제이다.

알고리즘은 그리디를 사용했다.

생각보다 쉬워 보였는데, 많은 시도를 통해 정답을 찾았다.

문제는 다음과 같다.

---

알고리즘 설명

문제의 예시와 같은 그림이다.

(1부터 2까지 중에 책을 원하는 사람이 3명인 경우)

이 모든 데이터를, 끝나는 지점이 일찍 나올수록 앞쪽으로 오게 sorting을 했고, 그리고 그 중 더 빨리 시작하는 숫자로 다시 sorting을 하여,

데이터들을 보면서 맨 앞 번호부터 나열을 시도했다.

 

'왜 뒤부터 나열을 하였는가? 앞에서부터 해도 사람들이 책을 받지 않나?'라는 질문이 생길수도 있는데,

해당 경우를 보자.

3명의 사람들 중 1부터 4까지 원하는 사람 2명, 2만 원하는 사람 2명인 경우이다.

 

왼쪽 경우는, sorting을 시작부터 한 경우이다.

앞에 두 사람이 1번, 그리고 2번을 가져가서 마지막 사람은 책을 받지 못했다.

 

하지만 오른쪽 경우는 sorting을 뒤에 맞춰서 했기 때문에, 

2번을 원했던 사람이 책을 가져가고,

1-4를 희망했던 사람이 각각 1,3번 책을 가져간다.

 

코드는 다음과 같다.

 

import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    n,m=map(int,input().split())
    data=[list(map(int,input().split())) for _ in range(m)]
    data.sort(key = lambda x: (x[1],x[0]))
    answer=0
    visited=[False]*(n+1)
    for a,b in data:
        for i in range(a,b+1):
            if not visited[i]:
                visited[i]=True
                answer+=1
                break
    print(answer)