[Java] 백준 1931 : 회의실 배정

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

1.

문제를 처음 보았을 때 저번에 프로그래머스에서 풀었던 단속 카메라 문제와 유사하다고 생각했다.

그러나 해당 문제의 풀이법을 잊었을 뿐 더러, 그 문제를 다시 풀어보았지만 이 문제에 적용시키기에 어려움을 느꼈다.

 

 

2.

이 문제를 풀기에는 다음과 같이 세 가지의 탐욕적 사고 방법이 있다.

• 회의 시작 시간을 기준으로

• 회의 종료 시간을 기준으로

• 회의 소요 시간을 기준으로

이 세가지 방법 중 첫 번째와 세 번째 방법은 반례가 존재하므로, 두 번째 방법을 선택한다.

 

회의가 빨리 종료되는 순으로 오름차순 정렬을 하여 선택을 하는데, 다음 선택할 회의의 시작 시간이 그 전 회의의 종료 시간보다 빠르면 선택하지 않는다.

 

 

3.

import java.util.Arrays;
import java.util.Scanner;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[][] meetings = new int[n][2];
        for (int i = 0; i < n; i++) {
            meetings[i][0] = sc.nextInt();
            meetings[i][1] = sc.nextInt();
        }

        Arrays.sort(meetings, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[1] == b[1]) {
                    return a[0] - b[1];
                }
                return a[1] - b[1];
            }
        });

        int answer = 0;
        int end = -1;
        for (int i = 0; i < n; i++) {
            if (meetings[i][0] >= end) {
                end = meetings[i][1];
                answer++;
            }
        }

        System.out.println(answer);
        sc.close();
    }
}

 

 

4.

정렬할 때 종료 시간이 같다면, 시작 시간이 빠른 순으로 정렬을 한다.

 

[참고] https://zoonvivor.tistory.com/52