백준 문제풀이 - 19598 번

링크 -> https://www.acmicpc.net/problem/19598

1. 요약 및 풀이방법

우선 회의 시작 시간과 종료 시간을 나누어 데이터로 정리하였습니다.
(start, 1), (end, -1) 로 나누어 리스트에 담아 오름차순으로 정렬 후,
index 1의 state값을 누적하며 최대 누적치를 구하였습니다.

회의는 시작하면 무조건 종료되기 때문에 누적값은 최종 0이 되며,
끝나지 않은 상태에서 다른 회의가 시작되면 새로운 회의실이 필요하기 때문에, 최댓값이 문제의 해답이 됩니다.

2. Code

def main():
    N = int(input())
    schedules = []
    for _ in range(N):
        start, end = map(int, input().split())
        schedules.append((start, 1))
        schedules.append((end, -1))
    schedules.sort()

    rooms = 0
    count = 0
    for schedule in schedules:
        count += schedule[1]
        rooms = max(rooms, count)

    print(rooms)

if __name__ == "__main__":
    main()

3. 학습 내용

처음에는 start 또는 end time을 기준으로 정렬해야 하기 때문에,
schedules = sorted(schedules, key=lambda x: x[0])
와 같이 정렬하였습니다.
이 경우 아래의 문제가 발생하였습니다.

2
10 20
5 10

sort -> [(5, 1), (10, 1), (10, -1), (20, -1)]

time이 같은 경우, 종료 후 같은 회의실을 사용해야 하는데
start가 먼저 정렬이 되면 문제가 발생합니다.

따라서 다음과 같이 수정하여 모든 값에 대해 오름차순을 확인 하여
time이 같은 경우, -1이 먼저 더해지도록 하였습니다.
schedules.sort() 로 정렬한 경우,

2
10 20
5 10

sort -> [(5, 1), (10, -1), (10, 1), (20, -1)]

4. 결과