백준 1931 파이썬 회의실 배정

백준 1931 - 회의실 배정

문제

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

1931번: 회의실 배정

1931번

답안 코드 :

N = int(input())

A = [[0] * 2 for _ in range(N)]

for i in range(N):

    S, E = map(int, input().split())

    A[i][0] = E  # 종료시간 우선 정렬이 우선이기 때문에 0번째에 종료시간을 먼저 저장.

    A[i][1] = S

A.sort()

count = 0

end = -1

for i in range(N):

    if A[i][1] >= end:  # 겹치지 않는 다음 회의가 나온 경우

        end = A[i][0]  # 종료 시간 업데이트

        count += 1

print(count)

생각 :

# 문제 분석
# 최대한 많은 회의 배정하기
# 그리디 활용
# 회의의 종료시간이 빠를수록 다음 회의 넣기에 유리하다
# 따라서 종료 시간이 빠른 순서대로 정렬해서 겹치지 않게 적절하게 선택해서 해결

# 문제 풀이
# 회의 시간 데이터를 저장하고 종료시간이 빠른 순서대로 정렬
# 종료시간 같으면 회의 시작 시간 기준으로 정렬

# 순차적 탐색하다가 겹치지 않는 회의나오면 하나씩 선택

 

그리디 알고리즘 정리 블로그

https://mkisos.tistory.com/entry/%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90

그리디 알고리즘과 우선순위 큐