BJ_G5_19598_최소 회의실 개수 - Java

[문제링크]

https://www.acmicpc.net/problem/19598

19598번: 최소 회의실 개수

---

[문제]

서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.

---

[입력]

첫째 줄에 배열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231−1보다 작거나 같은 자연수 또는 0이다.

---

[출력]

첫째 줄에 최소 회의실 개수를 출력한다.

---

[예제 입력 1]

3
0 40
15 30
5 10

---

[예제 출력 1]

2

 

---

[예제 입력 2]

2
10 20
5 10

---

[예제 출력 2]

1

 

---

[설명]

이 문제는 그리디 알고리즘 문제이다.

백준 11000번의 강의실배정 문제와 굉장히 비슷한 문제이다.

PriorityQueue를 사용하여 끝나는 시간들을 저장한다.정렬을 하고 PriorityQueue에 있는 끝나는 시간보다 rooms의 시작하는 시간이 더 크면 같은 방에서 회의가 가능하므로 pq에서 하나를 빼주고 모든 경우의 끝나는 시간을 pq에 넣어준다.끝나면 pq의 길이가 강의실의 총 개수가 된다.

 

 

백준 알고리즘 19598번 JAVA풀이

 

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scann = new Scanner(System.in);
		int N=scann.nextInt();
		Room[] rooms = new Room[N];
		for(int i=0;i<N;i++) {
			int start=scann.nextInt();
			int end=scann.nextInt();
			rooms[i]=new Room(start, end);
		}
		
		Arrays.sort(rooms, (r1, r2) -> r1.start == r2.start ? r1.end-r2.end : r1.start-r2.start);
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		pq.offer(rooms[0].end);
		for(int i=1;i<N;i++) {
			if(pq.peek()<=rooms[i].start) {
				pq.poll();
			}
			pq.offer(rooms[i].end);
		}
		System.out.println(pq.size());
	}
	
	public static class Room{
		int start;
		int end;
		public Room(int start, int end) {
			super();
			this.start = start;
			this.end = end;
		}
	}
}

 

 

 

궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.