Baekjoon[1931] - 회의실배정

링크

1931번: 회의실배정

문제설명

• 그리디

문제풀이

• 그리디

문제코드

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

public class Main1931 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/baekjoon/1931.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int ans=0;
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int [N][2];

        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[]>() {
            public int compare(int[] o1, int[] o2) {
                if(o1[1]==o2[1]) {;
                    return o1[0]-o2[1];
                }
                else {
                    return o1[1]-o2[1];
                }
            };
        });

        int end=-1;
        end = arr[0][1];
        ans++;
        for (int i = 1; i <N ; i++) {
            if(end<=arr[i][0]) {
                end=arr[i][1];
                ans++;
            }
        }

        System.out.println(ans);

    }
}

아쉬운점

• 문제 제대로 안읽음

  • 최소 회의 횟수가 아니라
  • 한번에 최대 사용할 수 있는 회의실 수임

• 그리디 안쓰면 O(N^2)이라 10^10이라 터짐

• 시작 시간 기준 정렬

  • O(N^2)

• 회의 시간 길이 기준 정렬

  • O(N^2)

• 끝나는 시간 기준 정렬 (꼼꼼히 정렬)

  • 시작 시간 기준으로도 정렬해야함

  • (3,4)->(4,4)여야하는데 (4,4), (3,4)가 input으로 주어질 수 있음

잘한점

• 그리디 생각

  • 끝나는 시간 기준 정렬