[BOJ] 1931 회의실 배정

회의실 배정

풀이

• 한 개의 회의실이 있고, 사용하고자 하는 N개의 회의가 있다.
• 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아라.
• 각 회의가 겹치지 않게, 회의실을 사용할 수 있는 회의의 최대 개수 이므로, 끝나는 시간을 기준으로 회의를 오름차순 정렬을 한다.
• Comparator 를 이용해서, 끝나는 시간이 같을 경우 시작 시간이 빠른 순으로 정렬한다.
• 그리고 나서, for문으로 순회하면서 차례대로 시작시간이 지금 기준이 되는 끝나는 시간보다 늦으면, cnt를 늘리고, 기준 끝나는 시간을 갱신한다.

🙆‍♀️ 정답 풀이

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][2];
        StringTokenizer st;
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1] == o2[1]){
                    return Integer.compare(o1[0],o2[0]);
                }
                return Integer.compare(o1[1],o2[1]);
            }
        });
        int cnt = 1;
        int start = arr[0][0];
        int end = arr[0][1];
        for(int idx=1;idx<N;idx++){
            if(end<=arr[idx][0]){
                cnt++;
                end = arr[idx][1];
            }
        }
        System.out.println(cnt);
    }
}