[Python] 백준 1931번 - 회의실 배정

1. 문제정보

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

1931번: 회의실 배정

 

2. 해결전략

1. 중첩되는 조건 구현하기
2. 중첩되었을 때 어떻게 해야 가장 많은 회의를 진행할 수 있을지 고민
   1. 회의시간을 오름차순으로 정렬하고 종료시간이 빠른 것부터 쌓아 나간다면 가장 많은 회의를 진행할 수 있을 거라는 생각

 

3. 코드

N = int(input())
schedule = []
for i in range(N):
    schedule.append(list(map(int,input().split())))\

# 오름차순 정렬
schedule.sort()

result = []
for i in schedule:
    input_start, input_end = i[0], i[1]

    if len(result) == 0:
        result.append([input_start, input_end])
        continue
    
    # 새로운 input이 중첩되는 경우
    start, end = result[-1][0], result[-1][1]
    if input_start >= start and input_start < end:
        # 중첩이 되었을 때 종료 인덱스가 더 짧은 좌표를 기준으로 함
        if input_end < end:
            result[-1] = [input_start, input_end]
    # 중첩되지 않는 경우 append
    else:
        result.append([input_start, input_end])
print(len(result))