[그리디, 파이썬] 백준 1931. 회의실배정

문제 : 한 회의실에 최대 몇개의 회의가 배정될 수 있는가

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

---

코드1 : 시간초과, 오답

import sys
sys.stdin = open('.//그리디//in.txt','rt')

n = int(input().rstrip())
meeting = [list(map(int, input().split())) for _ in range(n)]
# print(meeting)
cnt = 0
meeting.sort()
print(meeting)
lst = []
lst.append([meeting[0][1]])
for i in meeting[1:]:
    s,e = i[0], i[1]
    # s 시작, e 끝
    if lst[0][-1] <= s: # 다음회의보다 일찍 끝
        lst[0].append(e)
    else:
        lst.append([e])
    lst.sort()
long = 0
for r in lst:
    long = max(long, len(r))
print(long)

불필요한 sorting이 중복해서 들어감. 한 회의실에 최대 회의가 몇개까지 들어가느냐를 물어보는 거기 때문에 어떤 강의가 들어갔는지 전부 리스트로 나타낼 필요가 없다. 앞으로 나올 코드는, 회의가 빨리 끝나는 걸 기준으로 정렬했기 때문에 (그리디) 순서대로 비교해서 개수만 세면 됨.

코드2 : 내 코드

lambda 넣어서 솔팅하는 거, 두 요소 다 써줘야 되고 끝나는 시간 기준으로 정렬한다는 걸 유의해야 함. x[1]만 하면 틀림 처리됨

import sys sys.stdin = open('.//그리디//in.txt','rt')
input = sys.stdin.readline  
n = int(input().rstrip())  
meeting = [list(map(int, input().split())) for _ in range(n)\]  
meeting.sort(key=lambda x: (x[1], x[0]))

ss, ee = meeting[0][0], meeting[0][1]  
cnt = 1

for i in meeting[1:]:  
s,e = i[0], i[1]  
if ee <= s: # 다음회의보다 일찍 끝  
cnt += 1  
ee = e  
ss = s

print(cnt)

코드3: 예전에 보고 푼 코드. 가장 군더더기 없다

import sys  
sys.stdin = open('in.txt', 'rt')  
input = sys.stdin.readline  
n = int(input())  
meeting = []  
for i in range(n):  
s, e = map(int, input().split())  
meeting.append((s,e))  
et = 0  
m = 0  
meeting.sort(key = lambda x: (x[1], x[0]))

# 다시 푼 문제인데도 틀림, 문제 조건 해석(끝나는 동시에 시작가능, 시작하자마자 끝날 수 있음)이 어려웠고

# 끝나는 시간 같으면 시작시간 빠른거부터 정렬해야 한다는 게 이해가 안간다.

# 즉 sort 조건에 x[1]만 쓰는 게 아니라 둘다인게 이해가 안간다...

for s,e in meeting:  
if et <= s:  
m += 1  
et = e  
print(m)