[백준] 1931번 - 회의실 배정

 

그리디 알고리즘 문제 ....

최대한 많은 회의를 하기 위해서는 회의 종료 시간이 빨라야 한다!

서로 겹치지 않는 활동에 대해 종료시간이 빠르면 더 많은 활동을 선택할 수 있는 시간이 많아진다.

-- > 종료 시간을 기준으로 정렬!

 

BufferedReader를 사용하여 풀이하였다.

comparator를 재정의하여 

종료 시간이 같은 경우 시작 시간을 기준으로 오름차순 정렬,

그 외에는 종료시간을 기준으로 오름차순 정렬이 이루어지도록 하였다.

 

 

package 백준.greedy;

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 baekjoon_1931 {
    public static void main(String[] args) throws IOException {

        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 o1[0] - o2[0]; //첫 번째 요소 기준 정렬
                        }
                        return o1[1] - o2[1]; // 두 번째 요소 기준 정렬
                    }
                }
        );

        int count = 0;
        int prev_end_time = 0;

        for (int i = 0; i < arr.length; i++) {
            if (prev_end_time <= arr[i][0]) {
                prev_end_time = arr[i][1];
                count++;
            }

        }
        System.out.println(count);

    }
}