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

문제

1931번: 회의실 배정

---

풀이

 

a.  오답 및 시간 초과

import sys

n = int(input())
data = []
for i in range(n):
    data.append([j for j in map(int, sys.stdin.readline().split())])

# 회의 시간이 짧은 순으로 정렬했음 -> 이러면 회의를 최대 갯수만큼 할 수 있을 거라고 생각했는데
# 반례 n=3, data = [[3,5],[1,4],[4,8]]
data.sort(key=lambda x: x[1] - x[0])

# 회의실 사용 여부
_usage = [0 for i in range(max(x[1] for x in data) + 1)]

answer = 0
time = 0
for x in data:
    if 1 not in _usage[x[0]:x[1]]:
        answer += 1
        for i in range(x[0], x[1]):
            _usage[i] = 1
        if x[0] == x[1]:
            _usage[x[0]] = 1

print(answer)

b.  풀이

import sys

n = int(input())
data = []
for i in range(n):
    data.append([j for j in map(int, sys.stdin.readline().split())])

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

answer = 0
time = 0
for x in data:
    if time <= x[0]:
        time = x[1]
        answer += 1

print(answer)