[BOJ/python] 1931번 회의실 배정

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

1931번: 회의실 배정

문제 해석

 

회의 시간이 주어진다. 한 회의실에서 최대한 많이 회의를 할 수 있는 갯수를 출력하는 문제.

---

코드

 

# BOJ 1931
n = int(input())
arr = []
for i in range(n):
    start, end = map(int, input().split())
    arr.append((start, end))

# 정렬 / 우선순위 1 = 회의 종료시간이 작은 순서대로, 2 = 회의 시작 시간이 작은 순서대로 
arr = sorted(arr, key = lambda x: [x[1], x[0]])
ans = 1
start, end = arr[0][0], arr[0][1]
for i in range(1, n):
    s, e = arr[i]
    # 다음 회의 가능하면 += 1 / 시작시간, 종료시간 최신화
    if end <= s:
        start, end = s, e
        ans += 1

print(ans)

---

문제 풀이

 

1. 회의 시작 시간, 회의 종료 시간 순으로 정렬 후 차례대로 넣고, DFS 방식으로 완전 탐색 -> 시간초과

2. 회의 종료 시간, 회의 시작 시간 순으로 정렬 후 차례대로 넣기 -> 첫번째 원소를 지정했는데 또 처리해버림 -> 틀렸습니다.

3. 실수 정정 후 -> 맞았습니다.