Minystory

Algorithm/Baekjoon

[백준 1931] 회의실 배정 (Python)

2022. 8. 23. 11:32

문제 링크 #

https://www.acmicpc.net/problem/1931

문제 해설 #

Idea #

Sliding Window
슬라이딩 윈도우의 전형적인 문제로, 끝 시간을 기준으로 시간을 정렬해서 겹치지 않는 수를 계산

Time Complexity #

O(N) = 100,000

Data Size #

N: 1 <= int <= 100,000
t1,t2: 0 <= int <= 2^31-1

해설 코드 #

python

import sys
input = sys.stdin.readline

N = int(input())
times = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: [x[1],x[0]])
count, end_time = 0, 0

for t1,t2 in times:
    if t1 >= end_time:
        count += 1
        end_time = t2

print(count)