[boj] 백준 silver1 1931 회의실 배정 (Java) - 그리디

[문제]

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

[풀이]

이상하게 그리디에 머리가 잘 안돌아간다(다른 건 잘 돌아가는 줄ㅋ)...그래서 오늘은 그리디 데이로..

 

최대한 많은 회의실을 배정하려면 어떻게 해야 하는가? 그리디하게 종료시간이 빠른 순서대로 착착 회의실을 배정해주면 된다. 

종료시간이 빠른 순서대로 정렬 후, 그 다음 회의의 시작 시간이 현재 회의의 종료 시간과 같거나 더 늦다면 다음 회의실을 배정 받을 수 있다.

 

여기서 주의할 점은 정렬 시 종료 시간이 같다면 시작 시간이 빠른 순으로 정렬해줘야 한다는 것이다!!!

예를 들어, (시작 시간, 종료 시간)이 (3, 4)인 회의실과 (4, 4)인 회의실이 있다고 가정해보자. (3, 4)인 회의실이 먼저 배정을 받는 다면 (4, 4)인 회의실 사용이 가능하다. 하지만 (4, 4)인 회의실이 먼저 배정을 받는다면 (3, 4)인 회의실은 시작 시간이 종료시간 4보다 더 앞서있으므로 배정을 받지 못하게 된다. 이 경우만 고려해주면 된다.

 

[코드]

 

package 그리디;

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

public class boj_1931_회의실배정 {
    static int n;
    static int[][] times;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        StringTokenizer st;
        times = new int[n][2];
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            times[i][0] = Integer.parseInt(st.nextToken());
            times[i][1] = Integer.parseInt(st.nextToken());
        }

        //종료시간 오름차순 정렬
        Arrays.sort(times, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                if(o1[1]==o2[1]){
                    //종료시간이 같으면 시작 시간이 빠른 순으로
                    return Integer.compare(o1[0], o2[0]);
                }
                else return Integer.compare(o1[1], o2[1]);
            }
        });

        int end = times[0][1];
        int answer = 1;
        for(int i=1; i<n; i++){
            if(times[i][0] >= end){
                end = times[i][1];
                answer++;
            }
        }

        System.out.println(answer);
    }
    
}