[백준 1931번 / Java] 회의실 배정 - 탐욕법

문제 링크

Silver 1

 

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

1931번: 회의실 배정

 

 

---

 

 

풀이

최대의 경우의 수를 구하는 탐욕법을 요구하는 문제로

가장 많은 경우를 고려하기 위해 회의가 끝나는 시간으로 오름차순해주었고, 같을 경우 시작 시간으로 오름차순 해주었다.

Arrays.sort(discussing, 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];
    }
});

 

탐욕법을 구현하기 위한 조건만 잘 정하면 되는 문제였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BaekJoon1697 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;

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

        Arrays.sort(discussing, 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 end = discussing[0][1];
        int cnt = 1;
        for(int i = 1; i < discussing.length; i ++) {
            if(end <= discussing[i][0]) {
                cnt++;
                end = discussing[i][1];
            }
        }
        System.out.println(cnt);
    }

}