테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 강의실 배정 ======

===== 풀이 =====
  * 그냥 동시에 진행되는 강의가 가장 많은 순간의 강의 갯수가, 필요한 최소한의 강의실 수이다.
  * 각 강의를 [시작시간, 끝시간]의 구간으로 표현하면, 가장 많이 강의가 겹치는 구간을 찾으면 된다. 강의 시작시간과 끝시간을 모두 정렬한뒤, 스위핑하면서 현재 진행중인 강의 갯수를 업데이트 하는 식으로 처리할수 있다. 시간 복잡도는 정렬에 O(nlogn), 스위핑에 O(n), 총 O(nlogn)이다.
  * [[ps:problems:boj:19598]]도 n의 범위만 100,000으로 다를뿐 똑같은 문제이다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 11000. 강의실 배정".

- Problem link: https://www.acmicpc.net/problem/11000
- Solution link: http://www.teferi.net/ps/problems/boj/11000

Tags: [Sweeping]
"""

import sys

INF = float('inf')

END = 0
START = 1


def main():
    N = int(sys.stdin.readline())
    times = []
    for _ in range(N):
        S, T = [int(x) for x in sys.stdin.readline().split()]
        times.append((S, START))
        times.append((T, END))

    lecture_count = 0
    answer = max(
        (lecture_count := lecture_count + (1 if event == START else -1))
        for _, event in sorted(times))

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_5}}