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

백준 1931번

✔️ 문제 풀이

◾ 그리디 알고리즘

• 처음에는 dfs를 사용하여 문제풀이(한 마디로 전체 탐색...)
  ⇒ 시간초과
• 최적해를 구하는 논리를 생각해내는 것이 핵심!
• 입력값들을 기준에 따라 정렬한 후 그 배열을 돌면서 값을 구한다
• 이때 회의가 끝나는 시간이 늦는 케이스가 앞으로 오면, 그 이후에 회의를 시작하는 케이스들은 모두 회의를 시작할 수 없으므로 회의가 끝나는 시간(end)을 기준으로 배열을 정렬한다
• 왜 회의가 시작하는 시간(start)으로도 배열을 정렬해야 하는가❓
  ⇒ 배열이 time = [[4, 4], [2, 4]]와 같은 경우 끝나는 시간으로만 정렬해주면 답으로 1을 도출하지만, 실제 답은 2이다. 이와 같은 케이스를 고려하기 위해 꼭 시작하는 시간을 기준으로도 정렬해주어야 한다.
• 정렬된 배열을 돌면서 탐색하는 원소의 끝나는 시간(last)을 기억하고, 그 다음에 탐색하는 원소의 시작 시간이 last보다 크거나 같을 경우 cnt 값을 증가시키고, last 값을 업데이트 해준다.

최종 제출 코드

n = int(input())
time = []

for _ in range(n):
    start, end = map(int, input().split())
    time.append([start, end])

time = sorted(time, key=lambda a: a[0])
time = sorted(time, key=lambda a: a[1])

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