[Greedy][Java][BOJ] #19598. 최소 회의실 개수

#우선순위힙  #Gold5

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

🌷 문제 설명

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

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

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

입출력 예

입력	출력
3 0 40 15 30 5 10	2
2 10 20 5 10	1

 

💡 해결 포인트

1.  우선순위 힙
- 최소 힙(min heap)
- 가장 작은 값이 가장 먼저 나옴

2. 회의실을 1부터 추가하는 것이 아니라, 최대에서 빼가는 것

 

 

 

🌷 내 코드

1.  우선순위 힙

import java.io.*; 
import java.util.*;

public class BOJ_19598 {
  public static void main(String[] args) throws IOException {
    System.setIn(new FileInputStream("example.txt"));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine()); // 회의 수
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // 시작 시간 순서대로 정렬
    int[] start = new int[N]; // 시작 시간
    int[] end = new int[N]; // 끝나는 시간

    for (int i = 0; i < N; i++) { // 회의 시간 입력
      String[] line = br.readLine().split(" "); 
      start[i] = Integer.parseInt(line[0]); // 시작 시간
      end[i] = Integer.parseInt(line[1]); // 끝나는 시간
    } 

    Arrays.sort(start); // 시작 시간 정렬
    Arrays.sort(end);

    int count = 0;
    int max = 0; // 최대 회의실 갯수

    for (int i = 0; i < N; i++) { // 최소 회의실 갯수 구하기
      while (!pq.isEmpty() && pq.peek()[0] <= start[i]) { // 시작 시간보다 빨리 끝나는 회의가 있는 경우
        pq.poll(); // 끝나는 시간이 빠른 회의를 빼기
        count--; // 회의실 하나 빼기
      }

      pq.add(new int[] {end[i], start[i]}); // 끝나는 시간, 시작 시간 순서대로 추가 // 시작 시간보다 빨리 끝나는 회의가 없는 경우
      count++;

      max = Math.max(max, count);
    }

    System.out.println(max);
  }
}

 

 

🌷 코멘트

일주일치 치매예방 끗..! 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!
~대가리 꽃밭인 디지털 노마드가 꿈이예요~
🧚‍♀️ Gyumin Lee
📧 gyumin.q.lee@gmail.com