[BOJ] 1931. 회의실배정

그리디 알고리즘이다.

정확히 말하면 Interval Scheduling Greedy Algorithm 이다. 시간이 정해진 어떤일을 함에 있어 가장 문제에 따라 가장 최적의 효율을 낼수 있는 방법을 찾는 알고리즘이다. 이 알고리즘은 여러가지로 접근할 수 있다.
1. 일의 소요시간이 가장 짧은 순서로 접근
2. 일의 시작시간이 빠른 순서로 접근
3. 일의 끝시간이 빠른 순서로 접근

이 문제는 3번의 방법인 일의 끝 시간 기준으로 접근하여 보았다. 모든 노드들을 일의 끝시간으로 정렬을 한다음, 맨 처음 것을 선택 그 후 부터 다음에 나오는 노드의 시작점이 현재 노드의 끝점보다 같거나 크다면 선택후 현재 노드를 갱신해주는 방식으로 풀었다.

이와 비슷한 문제로 모든 회의를 수용하기 위해 회의실이 최대 몇개가 필요하냐 문제도 있는데, 그 문제는 2번의 방식으로 접근이 가능하다. 회의를 시작시간 순서로 정렬후 현재 노드의 끝시간과 다음번노드의 시작시간을 비교해가면서 queue를 이용하여 최대 회의실을 찾는 방법을 쓸수 있다.

Interval Scheduling 알고리즘은 문제에 따라 여러방법으로 접근해야한다. 연습이 필요한 그리디 유형이다.

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);
    }
    
}