회의실 배정 문제 응용하기 -모든 수업을 가능하게 하는 회의실의 수는-

1. 문제 11000번: 강의실 배정 (acmicpc.net) 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si = 현재 종료시간"이면 하나의 회의실에서 가능하다는 알고리즘으로 해결했다 근데 이 문제는 모든 수업을 가능하게 하는 최소의 회의실 수를 구해야한다 어떻게 하냐면 시작시간이 빠른 순서대로 오름차순 정렬한다 먼저 가..

• format_list_bulleted 그리디 알고리즘
• · 2022. 10. 18.
• textsms

탐욕 알고리즘 - 회의실 배정문제 해법 -

1. 문제 유형 1-1) 예시 윤대리는 소프트웨어 개발팀들의 회의실 사용 신청을 처리하는 업무를 한다. 이번 주 금요일에 사용 가능한 회의실은 하나만 존재하고 다수의 회의가 신청된 상태이다. 회의는 시작 시간과 종료 시간이 있고 회의 시간이 겹치는 회의들은 동시에 열릴 수 없다. 가능한 많은 회의가 열리기 위해 회의실은 어떻게 배정해야할까? 1-2) 정형화 시작시간과 종료시간 $(s_{i}, f_{i})$가 있는 n개의 활동들의 집합 $A = \left\{ A_{1}, A_{2},... , A_{n} \right\}$이고 i는 1이상 n이하이다. 여기서 서로 겹치지 않는 최대 개수의 활동들의 집합 S를 구하는 문제 2. 문제 해법 모든 경우의 수를 조사할 수도 있지만 탐욕 알고리즘이 가능한 대표적인 문제..

• format_list_bulleted 그리디 알고리즘
• · 2022. 9. 26.
• textsms