[JAVA] 백준 1931 그리디

 

 

 

문제

회의실의 사용시간 (start, end)가 주어졌을 때 최대한 회의를 많이할 수 있는 횟수를 구하여라

풀이

회의가 종료되는 시간이 짧은 회의를 우선으로 두고 구하였다.

정렬

Arrays.sort(A, 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 answer = 0;
        int now = 0;
        for(int i=0; i<N;i++){
            if(A[i][0] >= now) {
                answer++;
                now = A[i][1];
            }
        }

now값을 이전에 선택된 회의의 종료 시간으로 두고 이전의 종료시간이 i번째 회의의 시작시간보다 작거나 같다면 선택되도록 계산하였다.

전체 코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[][] A = new int[N][2];

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

        // 종료시간이 짧은 것 우선
        Arrays.sort(A, 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 answer = 0;
        int now = 0;
        for(int i=0; i<N;i++){
            if(A[i][0] >= now) {
                answer++;
                now = A[i][1];
            }
        }

        System.out.println(answer);

    }

}

결과