1 분 소요

1931번: 회의실 배정

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다.

각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고,

각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

회의의 시작시간과 끝나는 시간이 같을 수도 있다.

이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.


입력 조건

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데

이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.

시작 시간과 끝나는 시간은 $2^{31}$-1보다 작거나 같은 자연수 또는 0이다.


출력 조건

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


첫 번째 시도 .

n = int(input())

time=[]
for i in range(n):
  a,b = map(int,input().split())
  time.append((a,b))

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

result=0
end=0
for i,j in time:
  if i >= end:
    end = j
    result+=1
print(result)

»intput

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

»output

4

success

image-20220301203453262


🌝 Thinking

[아이디어]

  1. 각 회의를 (시작 시간, 끝나는 시간)와 같이 튜플 형태로 리스트에 저장한다.
  2. 리스트를 정렬한다. 우선순위는 끝나는시간(오름 차순), 시작 시간(오름 차순) 이다.
  3. 선택된 회의의 끝나는 시간 이랑 같거나 큰 시간이 다음 회의 시작시간이 된다.

⭐ 시작시간이 같은 회의일지라도 정렬의 규칙에 의하여 회의 시간이(끝나는시간 - 시작시간) 짧은 회의가

앞쪽으로 배치된다. 따라서 선택된 회의가 끝나는 시간 직후에 시작할수 있는 회의를 바로 진행하면 된다.



💡 깨달은 점.

  1. lambda x 를 이용하여 정렬에 우선순위를 줄 수 있다.

댓글남기기

참고