[백준/11000] 강의실 배정 (Java)
Question
- 문제 링크 : https://www.acmicpc.net/problem/11000
- 분류 : 우선순위큐
- 풀이 시간 : 40분
문제 해설
- Si에 시작해서 Ti에 끝나는 N개의 수업이 주어짐
- 모든 수업을 가능하게하는 최소 강의실의 개수는?
Solution
풀이 접근 방법
-
최대한 많은 강의 진행하는 문제 ~ -> "끝나는 시간 오름차순 정렬"이라고 생각하고 풀면 틀림!!
- 끝나는 시간 오름차순은 하나의 강의실에서 최대한 많은 수업을 진행하려할 때 해당됨!!
-
강의실이 비는 시간을 최소화 해야 함 = 강의 끝나는 시간과 다음 강의 시작 시간 사이의 텀이 작아야 함
- 강의 시간 오름차순 정렬해서 끝나는 대로 빨리 시작하는 강의 넣어야 함
- 반례 확인
-
강의 시간 오름차순 -> 강의 정보 객체(Session Class) 만들어서 우선순위 큐에 넣고 하나씩 뺌
-
빨리 끝나는 강의 알기 위해 -> 강의 끝나는 시간을 우선순위 큐에 넣고 관리
정답 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static class Session implements Comparable<Session> {
int start, end;
public Session(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Session o) {
// 시작시간 오름차순
if (Integer.compare(this.start, o.start) == 0) {
// 시작시간이 같다면, 종료시간 오름차순
return Integer.compare(this.end, o.end);
}
return Integer.compare(this.start, o.start);
}
}
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.valueOf(br.readLine());
// 시간시간 오름차순 순서대로 강의 담음
PriorityQueue<Session> sessions = new PriorityQueue<Session>();
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.valueOf(st.nextToken());
int end = Integer.valueOf(st.nextToken());
sessions.add(new Session(start, end));
}
// 강의실 개수 변수 : 1개로 시작
int classCnt = 1;
// 강의실별 끝나는 시간을 저장하는 큐 : 빨리 끝나는 강의싱이 우선순위 높음
// 큐의 사이즈 = 오픈한 강의실 개수
PriorityQueue<Integer> endQueue = new PriorityQueue<>();
// 첫 강의실에서 진행하는 강의의 끝나는 시간 넣음
endQueue.add(sessions.poll().end);
// 모든 강의가 강의실에 들어갈 때 까지
while (!sessions.isEmpty()) {
Session current = sessions.poll();
// 제일 빨리 끝나는 강의실의 종료 시간이 현대 시작해야할 강의보다 빠르면
if (endQueue.peek() <= current.start) {
// 해당 강의실 수업 종료
endQueue.poll();
} else {
// 제일 빨리 끝나는 강의보다 시작 시간이 더 빠르면
// 새로운 강의실 오픈
classCnt++;
}
// 수업 종료한 강의실 || 새로 오픈한 강의실에 강의 넣음
endQueue.add(current.end);
}
bw.write(classCnt + "\n");
bw.flush();
bw.close();
}
}
Author And Source
이 문제에 관하여([백준/11000] 강의실 배정 (Java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyunjkluz/백준11000-강의실-배정-Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)