[BOJ] 1931. 회의실 배정

1931. 회의실 배정

문제

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

입력

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

출력

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

회의실의 최대 개수를 구하는 문제
회의의 끝나는 시간에 맞추어 그 후 회의실이 정해지기 때문에
끝나는 시간을 기준으로 다음 회의를 결정하는 소스코드를 짰다

n = int(input())
array = []
for i in range(n):
  a, b = map(int, input().split())
  array.append((a, b)) # 시작과 끝나는 시간

array = sorted(array, key = lambda array : (array[1], array[0]))
# 1차 오름차순 기준 : array[1](끝나는 시간)
# 2차 오름차순 기준 : array[0](시작 시간)
# 끝나는 시간이 같을 때는, 시작 시간이 빠른 회의를 배치하는 것이 옳음

end = 0 # 회의 끝난 시간 초기화(다음 회의의 시작시간 전인지 체크)
idx = 0 # 시작 인덱스
result = 0 # 가능 회의 개수
while True:
  if idx == len(array): break
  i = array[idx]
  # 시작시간이 그 전 회의의 끝나는 시간 후인지 체크한다
  if i[0] < end: 
  # 이 경우는 시작시간이 끝나는 시간 전이므로, 해당 회의는 진행할 수 없음
  # 다음 회의 조건을 체크하기 위해 idx += 1
    idx += 1
    continue
  # 조건을 만족했을 때
  else:
    result += 1 # 회의 개수 + 1
    end = i[1] # 끝나는 시간 end에 저장
    idx += 1

print(result)

2번 87%까지 갔다가 실패하고 성공했는데
정렬 조건때문이었다
처음 작성한 소스코드는

def sort_value(t):
  return t[1]
array.sort(key = sort_value) # tuple 값으로 정렬

tuple이기 때문에, 함수를 하나 선언한 후 sort() 함수에 key 조건을 추가했다
끝나는 시간인 튜플[1]로만 정렬을 한 것이다.
하지만 끝나는 시간이 같을 때는 생각을 하지 않은 코드였다

array = sorted(array, key = lambda array : (array[1], array[0]))

lambda를 이용해 2개의 조건을 달 수 있도록 변경하였다
11652. 카드
이문제에서 파이썬 정렬 문법을 잠시 정리했는데..
역시 까먹고 다 찾아봤다ㅠ 그래서 제목도 다시 바꿈...
한번 파이썬 정렬 문법 정리한 글 포스팅해야겠다
정렬 & 배열 선언 & 입력 문법을 좀 더 알아가야겄다!

21.05.04 복습

import heapq

n = int(input())
arr = []
for _ in range(n):
  s,e = map(int, input().split())
  arr.append([s, e])

arr.sort(key = lambda x:(x[1], x[0])) # 끝나는 시간 기준으로 오름차순 정렬
save = [0]
ans = 0
for i in range(len(arr)):
  start, end = arr[i]
  comp_end = heapq.heappop(save) # 끝나는 시간과 비교해야 함.
  if start >= comp_end:
    ans += 1
    heapq.heappush(save, end)
  else:
    heapq.heappush(save, comp_end)

print(ans)

• 정렬 주의!

arr.sort(key = lambda x:(x[1], x[0])) # 끝나는 시간, 시작 시간 기준으로 오름차순 정렬

끝나는 시간으로만 정렬했다가 틀렸다. 끝나는 시간이 같을 때 시작 시간으로 오름차순 정렬을 해야 한다.