백준: 11000 강의실 배정

문제

11000번: 강의실 배정

 

문제 풀이

예제 입력 1의 경우의 수

 위의 그림과 같이 예제 입력 1의 경우, 최소로 필요한 강의실 개수가 2개임을 알 수 있다. 이를 계산하는 방법은 어렵게 생각할 필요 없이, 강의 시작 시간에 필요한 강의실 수를 증가시키고, 강의가 끝나면 필요한 강의실 수를 감소시킨다. 이때, 강의실 수의 최대 값을 구하면 필요한 최소 강의실 수를 구할 수 있다.

 

 문제를 풀기 위해서 주의할 점이라면, 입력되는 강의 시작 끝 시간에 시작인 경우는 +1, 끝인 경우는 -1과 같이 짝을 지어 따로 구성한다. 그 후, 정렬을 할 때 2가지 기준으로 정렬을 진행하여야 하는데 첫 번째는 시간, 두 번째는 +1인지, -1인지를 기준으로 정렬하여야 한다. (-1인 경우를 먼저 처리하여야 최소 회의실의 개수를 구할 수 있다.)

 

코드

from sys import stdin


if __name__ == "__main__":
    answer = 0
    N = int(stdin.readline())
    cnt = 0
    meeting = [0 for _ in range(N * 2)]

    idx = 0
    for start, end in [list(map(int, stdin.readline().split())) for _ in range(N)]:
        meeting[idx] = [start, 1]
        meeting[idx + 1] = [end, -1]
        idx += 2

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

    for _, state in meeting:
        cnt += state
        answer = max(answer, cnt)

    print(answer)

 이와 동일한 코드로 19598: 최소 회의실 개수도 풀 수 있다.