[백준] 1931번 : 회의실 배정 (java)

1931번: 회의실 배정 (acmicpc.net)

1931번: 회의실 배정

어떻게 생각하고 문제를 풀었는가?

한 회의실에서 진행 가능한 최대 회의의 수는 시작시간이 빠르고, 종료시간이 빠른 순으로 회의를 선택하는 경우입니다.

따라서 N개의 회의 정보를 종료시간과 시작시간에 따라 정렬한다면 문제를 해결할 수 있을 것이라고 생각하였습니다.

코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        StringTokenizer tokenizer;
        PriorityQueue<Reservation> reservations = new PriorityQueue<>();
        for(int i=0; i<N; i++){
            tokenizer = new StringTokenizer(reader.readLine());
            int start = Integer.parseInt(tokenizer.nextToken());
            int end = Integer.parseInt(tokenizer.nextToken());
            reservations.add(new Reservation(start, end));
        }
        reader.close();

        int max = 1;
        int previous = reservations.poll().end;
        while(!reservations.isEmpty()){
            Reservation current = reservations.poll();
            if(!current.isOverlap(previous)){
                max++;
                previous = current.end;
            }
        }
        System.out.println(max);
    }

    public static class Reservation implements Comparable<Reservation>{
        int start;
        int end;

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

        @Override
        public int compareTo(Reservation reservation){
            if(this.end > reservation.end)
                return 1;

            if(this.end < reservation.end)
                return -1;

            return this.start > reservation.start ? 1 : -1;
        }

        boolean isOverlap(int end){
            return this.start < end;
        }
    }
}

Priority Queue를 사용하여 문제를 해결하는 코드를 구현하였습니다.

회의의 시작시간과 종료시간을 담는 클래스 Reservation을 정의하고, Priority Queue에 삽입함으로써 정렬을 수행한 결과를 얻을 수 있습니다.

Priority Queue는 Comparable을 인자로 받거나, 클래스가 Comparable을 상속받아야 정렬을 수행할 수 있습니다.

저는 Comparable을 상속받고, compareTo를 오버라이딩하여 사용하였습니다.

종료시간이 작은 순으로 정렬하고, 종료시간이 같다면 시작시간이 작은 순으로 정렬이 이루어지도록 compareTo를 정의하였습니다.