사용자 도구

사이트 도구


ps:problems:boj:11000

강의실 배정

ps
링크acmicpc.net/…
출처BOJ
문제 번호11000
문제명강의실 배정
레벨골드 5
분류

스위핑

시간복잡도O(nlogn)
인풋사이즈n<=200000
사용한 언어Python
제출기록75868KB / 416ms
최고기록328ms
해결날짜2022/01/13

풀이

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

코드

"""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()

토론

댓글을 입력하세요:
F E​ W Z Z
 
ps/problems/boj/11000.txt · 마지막으로 수정됨: 2022/01/22 15:44 저자 teferi