백준 온라인 저지 – 19598번

몇 번 먹어보니 골드5가 뇌에 적당히 좋다는 생각이 들었습니다.

이번에는 골드 5를 선택하세요

선택한 문제 황금 5 최소 객실 수

(번역하다)

첫 번째 줄에는 회의 수

다음 줄부터 회의 시작 및 종료 시간이 표시됩니다.

3
0 40
15 30
5 10

위의 시간을 감안할 때,

(0, 40) 회의실 &

(5, 10) (15, 30) 회의실은 총 2개의 방이 필요합니다.

각 회의실은 별도로 사용할 수 있지만 최소한의 회의실은 확보해야 합니다.

2가 정답입니다

생각해보니 그리면 이해가 더 쉬울 것 같아서 이미지로 표현합니다.

(1, 4) (3,7) (6,10) (6, 8) (7,12)

위의 모임 시간을 일정으로 표현하면 다음과 같습니다.

다음 회의는 이전 회의가 끝난 후 시작할 수 있습니다(종료 시간 -1)만 표시

그려보니 3개의 회의실로 모든 회의가 가능하다는 것을 알 수 있었습니다.

코드로 이미지를 그려서 선을 확인할 수 없어서 다른 방법을 생각했습니다.

마지막으로 행의 수는 최대 겹침 구간으로 생각할 수 있습니다.

이것을 코드로 바꿔보십시오.

연대순으로 먼저 정렬

시작하다 시작하다 끝 끝내가 말했을 때

시간을 순환하는 동안 Start가 발생하면 행 수가 +1씩 증가하고 최대값이 업데이트됩니다.

끝에 도달하면 행의 개수는 -1이고 마지막 값을 확인한 후,

최대값만 출력됩니다.

import sys
N = int(sys.stdin.readline().rstrip())
conference = ()
count = 0
max_count = 0
for i in range(N):
    a, b = map(int, sys.stdin.readline().split())
    conference.append((a, 'start'))
    conference.append((b, 'end'))

conference.sort()
for _, info in conference:
    if info == 'start':
        count += 1
        if count > max_count:
            max_count = count
    else:
        count -= 1

print(max_count)

나에게 즉시 일어나지 않은 일들

그림을 그리면 이해하기 쉬워진다

코드로의 전환은 쉬웠습니다.

위와 같이 코드를 작성하고 360ms의 결과를 얻었습니다.

오늘 해결된 문제