백준 1931 회의실배정

 

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

1931번: 회의실배정

유명한 그리디 알고리즘 문제라고 한다. 회의시간이 가장 빠른 것을 기준으로 정렬을 해준다음 회의들을 순회하며 가장 빨리 끝나는 회의시간보다 늦게 시작하는 회의가 나올 때 마다 카운트를 하여 정답을 찾아냈다.

 

 

풀이

package 그리디_알고리즘;
import java.io.*;
import java.util.*;
public class 회의실배정
{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] meet = new int[n][2];
        for (int i = 0; i <n ; i++) {
            StringTokenizer st  = new StringTokenizer(br.readLine());
            meet[i][0] = Integer.parseInt(st.nextToken());
            meet[i][1] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(meet, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1]==o2[1]){
                    return o1[0] - o2[0];
                }
                else return o1[1]-o2[1];
            }
        });
        int endT = -1;
        int res = 0;
        for (int i = 0; i < meet.length; i++) {
            if(meet[i][0]>=endT){
                endT = meet[i][1];
                res++;
            }
        }
        System.out.println(res);
    }
}