[Baekjoon/🥈SilverⅡ] 1931: 회의실 배정

📃문제

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

📃입력

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

📃출력

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

🙋‍♀️접근 방법

🔔문제 속 핵심!

👩 문제 속에서 주의깊게 봐야 할 부분은 바로 ‘회의의 시작 시간과 끝나는 시간이 같을 수도 있다’는 부분이다.

• 예로 해당 입력들을 살펴보자.
  • N = 2
  • 1, 1/ 1, 1

  👩 이와 같이 주어졌을 때, 회의실을 사용할 수 있는 회의의 최대 개수는 몇개일까??

  • 답은 2개이다. 시작, 끝 시간이 같으므로 시작하자마자 끝나기 때문에 두 회의를 같은 시간에 넣어도 회의가 겹치지 않게 되는 것이다.

---

📃문제 분석

👩 회의실을 사용할 수 있는 회의의 최대 개수를 구하기 위해서는 짧게 걸리는 회의를 위주로 회의를 선택해야 한다.

👩 그렇다면 걸리는 시간 순으로 정렬을 해 작은 순으로 회의를 배치하면 될까??

그것은 아니다!!!

• 기본적으로 앞 회의가 언제 끝나느냐에 따라서 뒷 회의가 결정된다. 따라서 단순히 걸리는 시간 순이 아닌 우선 끝나는 시간 순으로 정렬해야 한다.
  • 그래야 해당 회의 이후의 회의들 중, 다음에 배치할 회의를 선택할 수 있게 된다.
• 그리고 여기서 추가적으로!! 시작하는 시간과 끝나는 시간이 같은 회의가 존재하기 때문에 끝나는 시간순으로 정렬한 후, 시작하는 시간순으로 추가 정렬해야 한다.
  • 필자는 시작하는 순으로 추가 정렬하지 않아 좀 고생했다..ㅎㅎ

👩‍💻 Algorithm

👩 그렇다면 위 내용을 기반으로 작성한 코드를 살펴보자.

#21.11.16
#그리디
import sys
N = int(sys.stdin.readline().rstrip())
lst = []
count = 0
for i in range(N):
  lst.append(list(map(int, sys.stdin.readline().rstrip().split())))
# 끝나는 시간을 기준으로 정렬 
# 끝나는 시간이 동일할 경우, 시작시간을 기준으로 정렬
lst.sort(key= lambda i : (i[1], i[0]))

k, l = lst[0] 
for j in range(1, N):
  n, o = lst[j]
  # 시작시간이 이전 회의의 끝나는 시간과 같거나, 그보다 클 때
  if n >= l:
    count += 1
    k, l = n, o

print(count + 1)

👩 그렇다면 그 과정을 자세히 살펴보자!!!

• 우선 끝나는 시간이 가장 빠른 회의가 기준이 된다. (lst[0])
• 기준을 제외한 나머지 회의들을 돌며 다음의 과정을 반복한다.
  • 기준 회의의 끝나는 시간보다 시작시간이 크거나 같을 때
  • 기준 회의는 회의실에 배치해도 되는 상황이다. (count + 1)
  • 기준 회의를 업테이트한다.

---

😶 여기서 잠깐!! 아마 다음의 과정에서 시작시간이 기준 회의의 시작시간보다 작을 경우는 왜 처리하지 않을까?

for j in range(1, N):
  n, o = lst[j]
  # 시작시간이 이전 회의의 끝나는 시간과 같거나, 그보다 클 때
  if n >= l:
    count += 1
    k, l = n, o

• 기준 회의보다 시작시간이 작을 경우 다음과 같이 정의된다.
  • 끝나는 시간은 기준회의보다 느리다.
  • 시작 시간은 기준회의보다 빠르다.

  ⇒ 결과적으로 회의시간이 기준회의보다 긴 회의이므로 고려할 필요가 없다!

---

🤷‍♀️ 그렇다면 왜 마지막에 count + 1을 해주는 것일까?

for문이 끝나는 경우, 상황은 두 가지가 존재한다.

• 상황1: 정렬 가장 마지막 회의가 기준이 되며 끝나는 경우
• 상황2: 기준 회의의 끝나는 시간보다 시작시간이 크거나 같은 회의가 없는 상태에서 for문이 종료된 경우

두 가지 상황에서 count + 1을 해야 하는 이유는 다음과 같다.

• 상황1: 마지막 회의도 회의실 배치에 포함되기 때문이다.
• 상황2: 기준회의도 회의실 배치에 포함되기 때문이다.

따라서 마지막에는 count에 1을 더한 값을 출력하게 된다.

그렇다면 이번 게시글은

여기서

이만 ~~ ~(˘▾˘~)

📃참고

• https://suri78.tistory.com/26
• https://pacific-ocean.tistory.com/236