Algorithm

백준[19598] 최소 회의실 개수

  • 문제: https://www.acmicpc.net/problem/19598
  • 분류: 그리디, 정렬, 우선순위큐
  • 난이도: G5
  • 소요시간: 15m
  • 자아성찰:
    • 처음에는 남은 회의 중 종료 시간이 빠른 순으로 배정된 회의실중 종료시간이 제일 빠른 회의실을 배정하면 되겠다라고 생각했다.
    • 스스로 테스트케이스를 생각해보면서, 다음 같은 상황에서 답이 맞지 않을 것 같았다.
      • 현재 배정된 회의실 중 종료시간은 30, 40
      • 남은 회의는 50-60 / 30-70
      • 50-60 회의가 종료시간 30 회의실 배정
      • 30-70 회의실은 종료시간 40 회의실 배정이 불가하므로 회의실 +1
      • 30-70 회의가 30 회의실을 먼저 배정받고, 50-60 회의가 40 회의실을 배정받으면 추가로 회의실 배정 필요없음
    • 시작시간이 빠른 순 / 시작시간이 같을 경우 종료시간 빠른 순으로 회의를 정렬하면 빨리 시작해야 하는 회의가 최대한 종료시간이 빠른 회의실을 먼저 배정받을 수 있겠다라고 생각했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class B_19598 {

    static int N, result;
    // 회의 시작 빠른 순 PQ
    static PriorityQueue<Meeting> meet = new PriorityQueue<>();
    // 회의실 종료시간 빠른 순 PQ
    static PriorityQueue<Integer> room = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            meet.add(new Meeting(start, end));
        }
        while (!meet.isEmpty()) {
            Meeting cur = meet.poll();
            // 회의실 새로 배정 (첫 회의 or 비어있는 회의실 없는 경우)
            if (room.isEmpty() || cur.start < room.peek()) {
                result++;
                room.add(cur.end);
            } else {
                // 기존 회의실 사용
                room.poll();
                room.add(cur.end);
            }
        }
        System.out.println(result);
    }

    static class Meeting implements Comparable<Meeting> {
        private final int start;
        private final int end;

        public Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }

        // 시작시간 빠른 순 / 같을 경우 종료시간 빠른 순
        @Override
        public int compareTo(Meeting obj) {
            if (this.start == obj.start) {
                return obj.end - this.end;
            }
            return this.start - obj.start;
        }
    }
}

'Algorithm' 카테고리의 다른 글

백준[21921] 블로그  (0) 2024.06.27
백준[15661] - 링크와 스타트  (0) 2024.05.27
백준[2529] - 부등호  (0) 2024.05.22
백준[2638] - 치즈  (0) 2024.05.16
백준[2583] - 영역 구하기  (0) 2024.05.15