January 15, 2022
백준 문제 링크 : https://www.acmicpc.net/problem/19598
모든 회의를 진행할 수 있는 최소 회의실의 개수를 구하는 문제이다. 즉 중복되는 회의가 생길 때마다 회의실의 개수를 추가해주어야한다.
정렬된 순서대로 시간에 따라 확인을 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class B_19598 {
static class pair {
public int start, end;
pair(int x, int y){
this.start = x;
this.end = y;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
PriorityQueue<pair> pq = new PriorityQueue<>((e1, e2) ->{
if(e1.start == e2.start) return e1.end - e2.end;
return e1.start - e2.start;
});
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int i=0; i<N; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
pq.add(new pair(start, end));
}
int cnt = 1;
q.add(pq.poll().end);
while(!pq.isEmpty()){
pair next = pq.poll();
// 꺼낸 회의가 겹칠 때 즉 q의 가장 앞에있는 end값보다 작을 때
if(next.start < q.peek()){
cnt++;
}
else{
q.poll();
}
q.add(next.end);
}
System.out.println(cnt);
}
}
기존회의실 문제에 약간의 변형이다. 즉 회의실 문제 기초문제를 잘 이해했다면 이런 문제는 쉽게 응요하여 해결할 수 있다. 기본이 중요하다.