[알고리즘] 백준 11000 강의실 배정 -그리디, 우선순위큐- 자바

 

www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

백준 그리디 유형 분류에 있는 문제이자 우선순위큐를 사용하여 풀 수 있는 문제입니다.

시작하는 시간과 끝나는 시간을 알려주는데 최대 몇개의 강의실이 필요한지 구하는 문제였습니다.

 

먼저 시간이 정렬되어서 입력이 안오므로 빠른시작시간순과 빨리 끝나는 순서로 정렬을 해줍니다.

그 후 우선순위큐를 사용하여 최대 몇개의 강의실이 필요한지 계산합니다. 

코드를 보면 이해할 수 있으니 자세한 내용은 생략하도록 하겠습니다.

 

 

 

풀이는 다음과 같습니다.

 

[Java]

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

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] times = new int[N][2];
        for (int i = 0; i < N; i++) {
            times[i][0] = sc.nextInt(); //Si
            times[i][1] = sc.nextInt(); //Ti
        }
        // 1. 시간순 정렬
        Arrays.sort(times, (o1, o2) -> {
            if (o1[0] == o2[0]) return o1[1] - o2[1]; //같은 시작시간일 경우 빨리 끝나는 순서로(끝나는시간오름차순)
            else return o1[0] - o2[0]; //시작시간 순 정렬
        });
        // 2. 강의실 개수 구하기
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            int start = times[i][0];
            int end = times[i][1];
            if (!queue.isEmpty() && queue.peek() <= start) { // 시작시간이 일찍 끝나는 시간보다 같거나 크다면 기존 강의실 이용
                queue.poll();
            }
            queue.offer(end);
        }
        System.out.println(queue.size());
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!