TIL) 1931 회의실 배정

이 포스팅은,
1. 미래의 내가 다시 이 문제를 풀고자 할 때 과거의 내가 어떻게 문제를 해결했었는지 알려주기 위해서
2. 같은 문제를 풀고 있는 사람에게 아이디어를 제공하기 위해서
작성되었습니다.

회의실 배정

백준 1931 회의실 배정 : https://www.acmicpc.net/problem/1931

💡 아이디어

첫 번째 풀이

N = int(input())


def choose_num(i, checked):
    if i > schedule[-1][0]:
        return checked
    min_num = 2**31-1
    for leng in range(len(schedule)):
        if schedule[leng][0] >= i:
            min_num = min(schedule[leng][1], min_num)
    checked.append(min_num)
    return choose_num(min_num, checked)


schedule = []
for _ in range(N):
    start, end = map(int, input().split())
    schedule.append([start, end, _])

schedule.sort(key=lambda x: x[0])

checked = []
print(len(choose_num(0, checked)))

위의 코드에는 엣지 케이스가 존재한다😭😭😭

😈 edge case 01
12
1 4
3 5
4 4
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

😈 edge case 02
2
1 2
2 2

이렇게 시간이 0인 회의가 존재할 경우 무한 루프를 돌게된다.

두 번째 풀이

import sys
input = sys.stdin.readline

N = int(input())

schedule = []
for _ in range(N):
    start, end = map(int, input().split())
    schedule.append((start, end))

schedule.sort(key=lambda x: (x[1], x[0]))
checked = 0

temp_start, temp_end = 0, 0
for i in range(len(schedule)):
    start, end = schedule[i]
    if i == 0:
        checked += 1
        temp_start, temp_end = start, end
    else:
        if start >= temp_end:
            temp_start, temp_end = start, end
            checked += 1
print(checked)

세 번째 풀이

# ...생략...

temp_start, temp_end = 0, 0
for start, end in schedule:
    if start >= temp_end:
        temp_start, temp_end = start, end
        checked += 1
print(checked)