백준_회의실 배정(1931) In Java

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

1931번: 회의실 배정

 

이 문제는 그리디 알고리즘의 대표적인 예로, 이렇게 시간표에서 최대한 많이 선택하는 문제를 활동 선택 문제(Activity Selection Problem) 이라고 부른다. ex) 활동 별 시간표을 문제에서 주어졌을 때 최대한 많은 활동을 선택하는 문제

 

접근방법

- 이러한 문제를 만났을 때 종료시간을 기준으로 정렬한다.

- 그 후 빨리 끝나는 것을 선택한다

 

풀이

- 회의 최대 갯수를 입력받은 후 회의 수를 2차원 배열의 행으로 , 열은 2로 선언한다

- 2열에서는 첫번째 열에 시작시간, 두번째 열에 종료시간을 입력 한다

- Arrays.sort()로 Comparator를 이용해 종료시간을 기준으로 정렬하고, 종료 시간이 같다면 시작시간이 빠른 순으로 정렬한다

- For 문을 통해서 시작시간이 그전 종료시간보다 빠르다면 1씩 더해간다 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N=Integer.parseInt(br.readLine());
        int[][] time=new int[N][2];
        for (int i = 0; i <N ; i++) {
            st=new StringTokenizer(br.readLine()," ");
            time[i][0]=Integer.parseInt(st.nextToken());
            time[i][1]=Integer.parseInt(st.nextToken());
        }

        Arrays.sort(time, new Comparator<int[]>() {

            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1]==o2[1]){
                    return o1[0]-o2[0];
                }
                return o1[1]-o2[1];
            }
        });

        int cnt=0;
        int prev=0;

        for (int i = 0; i < N; i++) {

            if(prev<=time[i][0]){
                prev=time[i][1];
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

 

참고 블로그

https://st-lab.tistory.com/145

[백준] 1931번 : 회의실배정 - JAVA [자바]