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

1931.회의실 배정(링크)과 유사한 그리디 유형의 문제였다.

문제를 마주하였을 때 회의실 배정 문제와 상당히 유사하여 비슷한 방식으로 풀게 되었다. 우선 적으로 모든 회의를 시작 시간 기준으로 우선순위 큐에 넣어 정렬을 하였다. 그 후 현재 가장 빠른 시각에 시작된 회의의 끝나는 시간과 그 바로 다음에 시작하는 회의의 시작 시간을 서로 비교하여, 만일 현재회의 끝시간 > 다음회의 시작시간 이면 회의실을 하나씩 추가하는 방식으로 구현해보았다. 

회의실 배정과 다른점은 회의실 배정은 하나의 회의실이기때문에 회의들을 1.끝나는 시간으로 회의정렬, 2. 현재 회의의 끝시간, 다음 회의의 시작시간 비교 이러한 방식으로 풀었지만, 이 문제는 회의실 자체를 늘리는 문제이기에 1. 시작 시간으로 회의정렬, 2. 현재 회의의 끝시간, 다음 회의의 시작시간 비교 방식으로 풀 수 있었다.

package study4;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main_bj_1931_회의실배정 {
    static class Node implements Comparable<Node>{
        int start, end;
        Node(int start,int end){
            this.start=start;this.end=end;
        }
        @Override
        public int compareTo(Node o) {
            if(end==o.end) {
                return Integer.compare(start, o.start);
            }
            return Integer.compare(end, o.end);
        }
    }
 
    static Node[] arr;
    static int N;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        N=Integer.parseInt(br.readLine());
        arr=new Node[N];
        for(int i=0;i<N;i++) {
            st=new StringTokenizer(br.readLine());
            int s=Integer.parseInt(st.nextToken());
            int e=Integer.parseInt(st.nextToken());
            arr[i]=new Node(s, e);
        }
        
        Arrays.sort(arr);
        
        
        int count =1;
        int curEnd=arr[0].end;
        
        for(int i=1;i<N;i++) {
            if(arr[i].start>=curEnd) {
                count+=1;
                curEnd=arr[i].end;
            }
        }
        
        System.out.println(count);
    }
    
}
 

 

하지만 이문제는 이런 방식으로도 풀 수 있지만, 단순하게 시작 시간, 끝 시간을 모두 입력받고 정렬 후 시작 시간을 마주하면 +1, 끝 시간을 마주하면 -1 하는 방식으로도 간단히 풀 수 있다.

package algosutdy1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_bj_19598_최소회의실개수 {
    static class Meeting implements Comparable<Meeting> {
        int time;
        boolean isStart;
 
        public Meeting(int time, boolean isStart) {
            this.time = time;
            this.isStart = isStart;
        }
 
        @Override
        public int compareTo(Meeting o) {
            return Integer.compare(time, o.time);
        }
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        PriorityQueue<Meeting> pq = new PriorityQueue<>();
 
        int N = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            pq.add(new Meeting(Integer.parseInt(st.nextToken()), true));
            pq.add(new Meeting(Integer.parseInt(st.nextToken()), false));
        }
 
        int meetingRoom = 0;
        int answer = 0;
 
        while (!pq.isEmpty()) {
            Meeting cur = pq.poll();
 
            if (cur.isStart) {
                meetingRoom += 1;
                answer = Math.max(answer, meetingRoom);
            } else {
                meetingRoom -= 1;
            }
        }
 
        System.out.println(answer);
    }
}