[Python] 백준 1931번_회의실 배정

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

1931번: 회의실 배정

 

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

• 입력
  • 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어짐
  • 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어짐
  • 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0
• 출력
  • 첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력
• 시간 제한: 2초
• 메모리 제한: 128 MB

 

"""
입출력 예시)

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

# -> (1,4), (5,7), (8,11), (12,14) 이용 가능
# => 사용 가능한 회의의 최대 개수: 4

 

 

## 의사코드 ##

# 다음 회의의 시작 시간이 이전 회의의 끝나는 시간보다 작으면 사용 불가
# -> 다음 회의의 시작 시간과 사용 가능한 이전 회의의 끝나는 시간 비교

# cnt = 1 # 사용 가능한 회의의 최대 개수(맨 첫 번째 회의는 사용 가능)
# time = [] # 전체 회의 시간을 담을 리스트
# available = [] # 사용 가능한 회의를 담을 리스트

# for i in range(1, n):
#     end_time = available[-1][1] # 사용 가능한 이전 회의의 끝나는 시간 
#     # 다음 회의 시작 시간이 사용 가능한 이전 회의의 끝나는 시간 보다 작은 경우 continue
#     if time[i][0] < end_time:
#         continue
#     # 다음 회의가 사용 가능한 경우
#     else:
#         cnt += 1 # 사용 가능한 회의의 최대 개수 + 1
#         available.append(time[i]) # 사용 가능 리스트에 time[i](다음 회의) 삽입

 

 

 

첫 번째 시도

 

n = int(input())

cnt = 1 # 사용 가능한 회의의 최대 개수(맨 첫 번째 회의는 사용 가능)
time = [] # 전체 회의 시간을 담을 리스트
available = [] # 사용 가능한 회의를 담을 리스트

# 회의 시간을 time 리스트에 담기
for i in range(n):
    start, end = map(int, input().split())
    time.append((start, end)) # [(시작 시간, 끝나는 시간)]

# 맨 첫 번째 회의를 사용 가능 리스트에 삽입
available.append(time[0])

for i in range(1, n):
    # 사용 가능한 이전 회의의 끝나는 시간 
    end_time = available[-1][1] # 사용 가능 리스트의 맨 마지막 원소의 index 1
    # 다음 회의 시작 시간이 사용 가능한 이전 회의의 끝나는 시간 보다 작은 경우 continue
    if time[i][0] < end_time:
        continue
    # 다음 회의가 사용 가능한 경우
    else:
        cnt += 1 # 사용 가능한 회의의 최대 개수 + 1
        available.append(time[i]) # 사용 가능 리스트에 time[i](다음 회의) 삽입

print(cnt)

-> 틀림

 

 

 

통과한 코드

 

n = int(input())

time = [] # 전체 회의 시간을 담을 리스트

# 회의 시간을 time 리스트에 담기
for i in range(n):
    start, end = map(int, input().split())
    time.append((start, end)) # [(시작 시간, 끝나는 시간)]

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

cur_end_time = 0 # 현재 회의의 끝나는 시간
cnt = 0 # 사용 가능한 회의의 최대 개수
for start, end in time:
    # 현재 끝나는 시간이 다음 회의의 시작 시간과 같거나 작은 경우
    if cur_end_time <= start:
        cur_end_time = end # 현재 끝나는 시간을 다음 회의의 끝나는 시간으로 변경
        cnt += 1 # 사용 가능한 회의의 최대 개수 + 1

print(cnt)

-> 끝나는 시간을 오름차순으로 정렬 후, 시작 시간 오름차순 정렬 추가, 사용 가능한 회의의 끝나는 시간을 리스트에 따로 저장하지 않고 조건에 맞으면 새로운 끝나는 시간으로 변경

 

 

• 끝나는 시간 오름차순 정렬 후, 시작 시간 오름차순 정렬

# 끝나는 시간을 오름차순으로 정렬한 후, 시작 시간을 오름차순 정렬
time = [(3, 3), (1, 3)]
time.sort(key=lambda x: (x[1], x[0]))
print(time)

"""
[(1, 3), (3, 3)]
"""

-> 두 회의의 끝나는 시간이 같은 경우, 시작 시간이 더 빠른 순서대로 정렬되어야 함

그래서 끝나는 시간을 기준으로 먼저 오름차순 정렬 후, 다시 시작 시간을 기준으로 오름차순으로 한 번 더 정렬

 

 

• 과정 확인

n = 11
time = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]


"""
현재 끝나는 시간: 0
다음 회의의 시작 시간: 1
사용 가능한 회의의 최대 개수: 0 

--------------------------------------------------
변경된 현재 끝나는 시간: 4
사용 가능한 회의의 최대 개수: 1
--------------------------------------------------

현재 끝나는 시간: 4
다음 회의의 시작 시간: 3
사용 가능한 회의의 최대 개수: 1 

현재 끝나는 시간: 4
다음 회의의 시작 시간: 0
사용 가능한 회의의 최대 개수: 1 

현재 끝나는 시간: 4
다음 회의의 시작 시간: 5
사용 가능한 회의의 최대 개수: 1 

--------------------------------------------------
변경된 현재 끝나는 시간: 7
사용 가능한 회의의 최대 개수: 2
--------------------------------------------------

현재 끝나는 시간: 7
다음 회의의 시작 시간: 3
사용 가능한 회의의 최대 개수: 2 

현재 끝나는 시간: 7
다음 회의의 시작 시간: 5
사용 가능한 회의의 최대 개수: 2 

현재 끝나는 시간: 7
다음 회의의 시작 시간: 6
사용 가능한 회의의 최대 개수: 2 

현재 끝나는 시간: 7
다음 회의의 시작 시간: 8
사용 가능한 회의의 최대 개수: 2 

--------------------------------------------------
변경된 현재 끝나는 시간: 11
사용 가능한 회의의 최대 개수: 3
--------------------------------------------------

현재 끝나는 시간: 11
다음 회의의 시작 시간: 8
사용 가능한 회의의 최대 개수: 3 

현재 끝나는 시간: 11
다음 회의의 시작 시간: 2
사용 가능한 회의의 최대 개수: 3 

현재 끝나는 시간: 11
다음 회의의 시작 시간: 12
사용 가능한 회의의 최대 개수: 3 

--------------------------------------------------
변경된 현재 끝나는 시간: 14
사용 가능한 회의의 최대 개수: 4
--------------------------------------------------

4
"""

 

 

 

 

 

참고)

 

https://kbwplace.tistory.com/128

[Python/파이썬] 백준 알고리즘 1931 - 회의실 배정 (Greedy Approach)

 

https://hei-jayden.tistory.com/33

[백준 파이썬] # 1931 회의실 배정