문제
서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.
입력
첫째 줄에 배열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231−1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최소 회의실 개수를 출력한다.
제한
- 시간 제한 : 2초
- 메모리 제한 : 256MB
문제 풀이 과정
위 문제와 아예 똑같은 방식이다.
심지어 코드도 똑같다.
먼저 start, end 를 입력 받고, 회의 시작 순으로 오름차순 정렬한다.
만약 회의 시작 시간이 같다면 끝나는 시간 기준으로 오름차순 정렬한다.
그후 우선순위큐에 첫 회의시간의 끝나는 시간을 넣는다.
우선순위큐에는 회의가 끝나는 시간이 오름차순으로 정렬되어 있을 것이다. 즉 먼저 끝나는 회의가 첫번째로 빠진다.
list를 순회하며 우선순위큐의 최상단에 위치한 회의 끝나는 시간보다, 다음 시작 시간이 같거나 크다면, 그 회의실을 사용할 수 있기 때문에 기존 회의 시간을 빼준다.
그리고 공통적으로 회의 끝나는 시간을 큐에 계속 추가해준다.
위 과정을 반복하면 결국 우선순위 큐에 겹치는 회의 끼리 쌓이게되며, 큐의 크기가 필요한 회의실 개수가 된다.
정답 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Main19598 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
List<Pair> list = new ArrayList<>();
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());
list.add(new Pair(start, end));
}
list.sort((o1, o2) -> {
if (o1.start == o2.start) {
return o1.end - o2.end;
}
return o1.start - o2.start;
});
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(list.get(0).end);
for (int i = 1; i < N; i++) {
if (pq.peek() <= list.get(i).start) {
pq.poll();
}
pq.add(list.get(i).end);
}
System.out.println(pq.size());
}
private static class Pair {
int start;
int end;
public Pair(int start, int end) {
this.start = start;
this.end = end;
}
}
}