- Published on
- •👁️
회의실 배정 ⭐
- Authors
- Name
- River
문제 설명
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
제한사항
- N의 범위는 1 이상 100,000 이하
- 시작 시간, 끝나는 시간의 범위는 0 이상 2^31-1 이하
입출력 예
입력
11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14
출력
4
설명
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
풀이 접근법
시간복잡도 : O(N log N)
공간복잡도 : O(N)
사용 알고리즘 :
그리디정렬우선순위 큐
핵심 포인트 :
- 끝나는 시간 기준 오름차순 정렬
- 종료시간이 같을 때는 시작시간 기준 오름차순 정렬 ⭐
- 가장 빨리 끝나는 회의부터 선택하는 그리디 전략
경계값/반례 :
- 회의의 시작시간과 끝나는 시간이 같은 경우
- 종료시간이 같은 회의들이 여러 개 있는 경우
핵심 아이디어
- 가장 빨리 끝나는 회의부터 선택하는 그리디 알고리즘
- 끝나는 시간이 빠른 순서로 정렬한 후, 각 회의를 순차적으로 검토하면서 이전 회의 종료 시간과 겹치지 않는 회의만 선택
- 종료시간이 같을 때는 시작시간이 빠른 순서로 정렬하여 최적해 보장
- 우리가 선택한 회의의 끝나는 시간이 곧 체크 타임이다.
해결 방법
- 회의를 끝나는 시간 기준 오름차순 정렬
- 이후 제거를 편하게 하기 위해 우선순위 큐 사용
- 첫 번째 회의 이후 다음으로 끝나는 시간이 빠른 회의를 꺼낸다.
- 꺼낸 회의의 시작 시간이 이미 지났으면 그냥 버린다.
- 아니라면, 해당 회의를 진행하고, 끝나는 시간을 다음 체크 타임으로 지정한다.
내부 해부 과정
tables = [[1,4], [3,5], [0,6], [5,7], [3,8], [5,9], [6,10], [8,11], [8,12], [2,13], [12,14]]
- 11개의 회의 데이터가 들어온다.
- 끝나는 시간을 기준으로 오름차순 정렬한다.
tables = [[1,4], [3,5], [0,6], [5,7], [3,8], [5,9], [6,10], [8,11], [8,12], [2,13], [12,14]]- checkTime = 0으로 초기화하고 회의를 하나씩 검토한다.
- 선택 과정
[1,4]: 0 ≤ 1 ⇒ ⭕ count=1, checkTime=4[3,5]: 4 ≤ 3 → 선택 안함 (이미 4시까지 회의 중)[0,6]: 4 ≤ 0 → 선택 안함[5,7]: 4 ≤ 5 ⇒ ⭕ count=2, checkTime=7[3,8]: 7 ≤ 3 → 선택 안함[5,9]: 7 ≤ 5 → 선택 안함[6,10]: 7 ≤ 6 → 선택 안함[8,11]: 7 ≤ 8 ⇒ ⭕ count=3, checkTime=11[8,12]: 11 ≤ 8 → 선택 안함[2,13]: 11 ≤ 2 → 선택 안함[12,14]: 11 ≤ 12 ⇒ ⭕ count=4, checkTime=14
- 결과 : 총 4개의 회의를 진행할 수 있다.
생각 과정
tables = [[1,4], [3,5], [0,6], [5,7], [3,8]]
❌ 처음 시도한 정렬 방식들
- 시작 시간 정렬 :
tables = [[0,6], [1,4], [3,5], [3,8], [5,7]]- 문제점 : 끝나는 시간이 크다면 너무 많은 경우를 포기해야 한다.
- 걸리는 시간 정렬 :
tables = [[3,5], [5,7], [1,4], [3,8], [0,6]]- 문제점 : 앞뒤 시간에 올 수 있는 여러 경우의 수를 모두 탐색해야 하므로 비효율적
- 끝나는 시간 정렬 :
tables = [[1,4], [3,5], [0,6], [5,7], [3,8]]- ✅ 최적 : 빠르게 끝나는 것을 먼저 확보하여 최대한 많은 수를 선택하기에 알맞다.
💡 1차 제출 후 발견한 문제점
예시
7 1 4 3 5 6 6 5 6 0 6 5 7 3 8문제에서 나와있듯 "회의의 시작시간과 끝나는 시간이 같을 수도 있다" 즉, 만약에 입력이 위와 같다면,
끝나는 시간 오름차순 정렬 :
tables = [[1,4], [3,5], [6,6], [5,6], [0,6], [5,7], [3,8]]- 1 :
[1,4]⇒ 통과 - 2 :
[3,5]⇒ X (checktime : 4 > starttime : 3) - 3 :
[6,6]⇒ 통과 - 4 :
[5,6]⇒ X (checktime : 6 > starttime : 5) - 5 :
[0,6]⇒ X (checktime : 6 > starttime : 0) - 6 :
[5,7]⇒ X (checktime : 6 > starttime : 5) - 7 :
[3,8]⇒ X (checktime : 6 > starttime : 3) - 총 2개의 회의를 진행할 수 있다.
- 1 :
먼저 [5,6] 진행한 이후에도 [6,6]은 진행할 수 있다.
다만 직접 만든 예시처럼 데이터가 들어왔을 때 끝나는 시간으로만 정렬한다면, 저런 요소를 놓치게 된다.
시작 시간에 대해서 추가 정렬이 필요하다.
끝나는 시간에 대해 오름차순, 이후 끝나는 시간이 같은 경우 시작 시간에 대해 오름차순 정렬을 한다면,
tables = [[1,4], [3,5], [0,6], [5,6], [6,6], [5,7], [3,8]]이렇게 나온다.- 1 :
[1,4]⇒ 통과 - 2 :
[3,5]⇒ X (checktime : 4 > starttime : 3) - 3 :
[0,6]⇒ X (checktime : 4 > starttime : 0) - 4 :
[5,6]⇒ 통과 - 5 :
[6,6]⇒ 통과 - 6 :
[5,7]⇒ X (checktime : 6 > starttime : 5) - 7 :
[3,8]⇒ X (checktime : 6 > starttime : 3) - ✅ 총 3개의 회의를 진행할 수 있다.
- 1 :
핵심 패턴
1️⃣ 그리디 알고리즘의 핵심
// 가장 빨리 끝나는 회의부터 선택
if (checkTime <= table.start) {
count++;
checkTime = table.end;
}
- 매 순간 최선의 선택(가장 빨리 끝나는 회의)을 하면 전체 최적해 달성
- 이전 회의 종료 시간과 현재 회의 시작 시간만 비교하면 됨
2️⃣ 안전한 comparator 작성
PriorityQueue<Table> pq = new PriorityQueue<>((a, b) -> {
if (a.end != b.end) {
return Integer.compare(a.end, b.end); // 끝나는 시간 오름차순
}
return Integer.compare(a.start, b.start); // 시작 시간 오름차순
});
Integer.compare()사용으로 오버플로우 방지- 이차 정렬 조건으로 최적해 보장
3️⃣ 우선순위 큐 활용
// 모든 회의를 큐에 넣고 하나씩 꺼내며 처리
for (int i = 0; i < n; i++) {
pq.add(tables.get(i));
}
while (!pq.isEmpty()) {
Table table = pq.poll();
// 선택 로직
}
- 자동 정렬로 코드 간결성 증대
- 큐에서 꺼내는 순서가 곧 검토 순서
1차 제출 코드 ❌
import java.util.*;
public class Main {
static class Table {
int start;
int end;
public Table(int start, int end) {
this.start = start;
this.end = end;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
List<Table> tables = new ArrayList<>();
for (int i = 0; i < n; i++) {
int start = sc.nextInt();
int end = sc.nextInt();
tables.add(new Table(start, end));
}
PriorityQueue<Table> pq = new PriorityQueue<>(
(a, b) -> a.end - b.end
);
for (int i = 0; i < n; i++) {
pq.add(tables.get(i));
}
int count = 0;
int checkTime = 0;
while (!pq.isEmpty()) {
Table table = pq.poll();
if (checkTime <= table.start) {
count++;
checkTime = table.end;
}
}
System.out.println(count);
}
}
정답 코드와 다른 점은 딱 하나이다.
PriorityQueue<Table> pq = new PriorityQueue<>( (a, b) -> a.end - b.end );- 끝나는 시간 기준 오름차순만 설정
정답 코드에서는 끝나는 시간이 같은 경우, 시작 시간 오름차순으로 추가 정렬한다.
PriorityQueue<Table> pq = new PriorityQueue<>( (a, b) -> { if (a.end != b.end) { return Integer.compare(a.end, b.end); } return Integer.compare(a.start, b.start); } );a - b와 같이 간단하게 표현할 수 있지만, 혹시 모를 것을 대비하여Integer.compare(a, b)사용- 커스텀 Comparator를 사용했다.
최종 제출 코드
import java.util.*;
public class Main {
static class Table {
int start;
int end;
public Table(int start, int end) {
this.start = start;
this.end = end;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
List<Table> tables = new ArrayList<>();
for (int i = 0; i < n; i++) {
int start = sc.nextInt();
int end = sc.nextInt();
tables.add(new Table(start, end));
}
PriorityQueue<Table> pq = new PriorityQueue<>(
(a, b) -> {
if (a.end != b.end) {
return Integer.compare(a.end, b.end);
}
return Integer.compare(a.start, b.start);
}
);
for (int i = 0; i < n; i++) {
pq.add(tables.get(i));
}
int count = 0;
int checkTime = 0;
while (!pq.isEmpty()) {
Table table = pq.poll();
if (checkTime <= table.start) {
count++;
checkTime = table.end;
}
}
System.out.println(count);
}
}