[백준/Python] 1901 회의실 배정 | 그리디(greedy)

📒 문제

---

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

 

🤸‍♀️ 문제 분석

---

처음에 괜히 복잡하게 접근했다가 시간초과 판정을 받았다.
- 처음에는 sort를 "가장 적은 회의 시간이 소요되는 회의"를 기준으로 오름차순 정렬(A)을 해서, 

- 회의 차지하는 빈 리스트(B)를 최대시간의 크기만큼 초기화하고,

- 회의정보를 담고 있는 리스트(A)를 앞에서부터 살피며, 회의를 차지하고, 차지한 경우 리스트(B)에 각 인덱스를 채워주고

- 아닌 경우 A 반복을 break 걸고..

뭐 이런식으로 복잡하게 접근했다.

 

💡 그러다가 sorting을

- 시작 시간 기준으로 오름차순 한번

- 끝나는 시간 기준으로 오름차순 한번 

하면 간단하게 풀 수 있다는 것을 깨달았다(=구글링했다)
 

해당 기준으로 하면 회의 시간이 빠른 순 => 그 중에서 회의 소요시간이 짧은 순으로 정렬이 되어, 회의 시간을 차곡차곡 쌓을 수 있다.

 

💡  겹치지 않게 하기위해 기존 회의의 끝나는 시간과 다음 회의의 시작 시간을 겹치지 않는지 확인만 하면 된다.

 

 

🧮코드

---

# 1931 회의실 배정

# n : 회의의 수
n = int(input())

# 회의정보 (시작시간, 끝나는 시간)
infos = [list(map(int, input().split())) for _ in range(n)]

# 회의 시작시간을 기준으로 오름차순 정렬
infos.sort(key = lambda x:x[0])
# 회의 끝나는 시간을 기준으로 다시 한 번 오름차순 정렬
infos.sort(key = lambda x:x[1])

# 맨 처음 회의 시작과 끝나는 시간은 리스트의 맨 앞 회의를 기준으로 잡는다
s = infos[0][0]
e = infos[0][1]

# result : 회의실을 사용할 수 있는 회의의 수
result = 1 # 첫 회의 포함이므로 1부터 시작

# 리스트 두 번째 회의부터 확인
for info in infos[1:]:
    # 기존에 진행하는 회의의 끝나는 시간보다 새로운 회의의 시작 시간이 크거나 같다면 회의가능
    if info[0] >= e:
        result += 1
        # 기존 진행 회의 시작, 끝 시간 재할당
        s = info[0]
        e = info[1]
         
print(result)