[백준 1931] 회의실 배정

문제

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

---

아이디어

그리디 알고리즘으로 접근할 수 있다. 그 근거를 살펴보자.

• 지금 시점에 시작할 수 있는 회의들 중에서 가장 빨리 끝나는 회의를 진행하면 된다. 
  • 시작 시간을 고려하면 안된다. 시작 시간 자체는 다음 회의를 탐색하는 데에 있어서 기준이 될 수 없다.
• 이번 회의가 일찍 끝나면 끝날수록 더 많은 다음 회의를 고려할 수 있다.

결론은, 일단 모르겠고 제일 먼저 끝나는 걸 찾자. 이다. 예를 들어보자.

회의 시간이 (1, 4), (2, 3), (3, 5) 라고 하자.

• 시작 시간 기준으로 정렬하면
  • (1, 4) 를 진행하면 끝난다. 즉, 1개의 회의만 진행할 수 있다. 
• 끝나는 시간 기준으로 정렬하면 (2, 3), (1, 4), (3, 5) 가 된다. 
  • 일단 (2, 3) 회의를 먼저 진행한다. (일찍 끝나니까 뭐가 됐든 다음 회의를 열 수 있으면 열면 되니까)
  • 회의가 3시에 끝났기 때문에 1시에 시작하는 (1, 4) 회의는 열 수 없다. pass
  • (3, 5) 회의는 진행할 수 있다. 
  • 이렇게 총 2개의 회의를 진행할 수 있다.

정리하자면, 끝나는 시간을 기준으로 정렬한 후에 각 회의에 대해 순회하면서 이번 회의의 시작 시간이 마지막 회의의 종료 시간 이후라면(같아도 된다. 그래서 if table[i][0] >= end에 등호가 들어간 것이다.), 회의를 배정하면 

# 오답 코드
n = int(input()) 
table = [list(map(int, input().split())) for _ in range(n)]
table.sort(key = lambda x: (x[1]))

cnt, end = 0, 0
for i in range(n) : 
    if table[i][0] >= end : 
        end = table[i][1]
        cnt += 1 
           
print(cnt)

 

안된다.

 

틀렸습니다ㅠ

 

왜 틀린걸까? 문제에 이런 말이 적혀있다.

회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

시작하자마자 끝낼거면 왜 배정해달라고 하는지 잘 모르겠지만, 아무튼 해달라고 하면 해줘야 하는 게 우리 역할인가보다.

회의 시간이 (2, 3), (3, 3), (3, 4)이면, (2, 3) 회의가 끝나자마자 (3, 3) 회의가 순식간에 지나가고 (3, 4) 회의까지도 진행할 수 있다는 뜻이다. 이 조건이 왜 중요한지 아래의 예시를 보자. 

 

이번엔 회의 시간이 (1, 4), (2, 3), (3, 3), (3, 5) 라고 하자.

• 끝나는 시간 기준으로 정렬하면 (3, 3), (2, 3), (1, 4), (3, 5) 가 된다. 
  • 일단 (3, 3) 회의를 먼저 진행한다. 
  • 회의가 3시에 끝났기 때문에 2시에 시작하는 (2, 3) 회의는 열 수 없다. pass
  • 마찬가지로 (1, 4) 회의도 진행할 수 없다.
  • (3, 5) 회의를 진행할 수 있다. 
  • 이렇게 총 2개의 회의를 진행할 수 있다.

딱히 얘기할 시간도 없는 (3, 3) 회의를 먼저 진행해버리는 순간 (2, 3) 회의는 진행할 수 없게 된다. 

하나의 회의만 열어야 한다면 쓸데없는 (3, 3) 회의는 버리는 게,,, 

하지만 우리는 어찌됐건 많은 회의를 배정하면 끝이다. (2, 3) 회의를 먼저 열고 (3, 3) 회의를 여는 건 가능하다.

즉, 끝나는 시간 기준으로 정렬한 뒤에 끝나는 시간이 같다면 시작하는 시간이 빠른 회의를 먼저 고려하도록 정렬하면 된다.  

• 위의 기준으로 정렬하면 (2, 3), (3, 3), (1, 4), (3, 5) 가 된다. 
  • 일단 (2, 3) 회의를 먼저 진행한다. 
  • 회의가 3시에 끝났기 때문에 3시에 시작하는 (3, 3) 회의도 열 수 있다.
  • 마찬가지로 (1, 4) 회의는 진행할 수 없다.
  • (3, 5) 회의를 진행할 수 있다. 
  • 이렇게 총 3개의 회의를 진행할 수 있다.

따라서 table.sort(key = lambda x: x[1]) 이 아니라, table.sort(key = lambda x: (x[1], x[0])) 이 제대로 된 정렬 방법이다.

---

Solution

n = int(input()) 
table = [list(map(int, input().split())) for _ in range(n)]
table.sort(key = lambda x: (x[1], x[0]))

cnt, end = 0, 0
for i in range(n) : 
    if table[i][0] >= end : 
        end = table[i][1]
        cnt += 1 
           
print(cnt)

 

이번엔 진짜 정답코드다