Jin의 일상

www.acmicpc.net/problem/9576

문제

1. N권의 책이 있다. 각 책에는 1부터 N까지 순차대로 번호가 매겨져 있다.

2. M명의 학생이 가지고 싶은 책의 번호를 a b 형태로 제출한다.

3. a부터 b까지의 책 중 남는 것이 있다면 한 개씩 받을 수 있다.

 - 남는 책이 없으면 받지 못한다.

4. 책을 받을 수 있는 최대 학생 수는?

알고리즘

1. 학생들이 제출한 목록을 "b를 기준으로 오름차순 --> a를 기준으로 내림차순" 한다.

2. 책의 분배 상태를 의미하는 리스트를 한 개 만든다.

 - 인덱스는 책의 번호를 의미한다.

 - 인덱스 값은 책을 분배했음(1), 분배하지 않음(0)을 의미한다.

3. 학생들이 제출한 범위 내에서 반복문을 진행하고, 책의 분배 상태를 확인한다.

 - 분배되지 않은 책을 발견하면, 리스트의 해당 인덱스를 1로 변경한 후 반복문을 종료한다.

* b를 기준으로 오름차순 한 이유

[1, 2]와 [2, 4]의 예제가 존재한다고 가정하자.앞선 학생이 갖는 선택지는 1과 2가 있다.뒷 학생이 갖는 선택지는 2, 3, 4가 있다.

만약 앞선 학생이 1번 책을 선택한다면, 뒷 학생은 온전히 2, 3, 4의 선택지를 갖게 된다.

하지만 만약 앞선 학생이 2번 책을 선택한다면, 뒷 학생은 3, 4의 선택지를 갖게 된다.

또한, [a, b]에서 b는 언제나 a보다 작거나 같다. (a<=b)

따라서 b가 낮은 학생들이 우선순위를 가져야 한다.

* a를 기준으로 내림차순 한 이유

b를 기준으로 오름차순한 상태에서 a를 기준으로 내림차순 한 이유는 다음과 같다.

예를 들어, [2, 3]과 [1, 3]이 존재한다고 하자.

앞선 학생의 경우의 선택지는 2와 3이 있다.

반면에 뒷 학생의 선택지는 1, 2, 3이 있다.

따라서 선택지가 더 적은 [2, 3]을 제출한 학생이 우선순위를 가져야 한다.

즉, a를 기준으로 내림차순 해야 한다.

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


n = int(input())
for _ in range(n):
    numBooks, numStudents = map(int, input().split())
    queue = [list(map(int, input().split())) for _ in range(numStudents)]
    queue.sort(key=lambda x: x[1])

    status = [0] * (numBooks+1)
    for i in range(numStudents):
        for j in range(queue[i][0], queue[i][1]+1):
            if status[j] == 0:
                status[j] = 1
                break
    print(sum(status))