[알고리즘 문제] 백준1931 - 회의실배정

이번 문제는 회의실배정문제로 그리디 알고리즘을 사용하여 풀 수 있는 문제입니다.

 

문제는 생각보다 어렵지 않습니다. N개의 회의와 각각의 회의의 시작시간과 종료시간이 있습니다. 다음 아래의 조건을 만족하도록 회의 시간표를 짜야하는데, 여기서 최대 사용할 수 있는 회의수를 출력하는 것입니다.

 

1. 회의진행시간이 겹치면 안된다.

2. 회의는 한번 시작하면 중간에 중단될 수 없다.

3. 회의의 시작시간과 끝나는 시간이 같을 수도 있다, 이는 시작하자마자 끝나는 것으로 간주한다.

 

예를들어서, 현재 회의 시간이 [ 1,4 ]이고 다음 회의시간이 [ 2,7 ]이라면, 이는 시간표에 등록될 수 없습니다. 하지만 [4, 8], [5, 5]인 경우는 시간표에 등록할 수 있겠죠. 왜냐하면 회의의 시작시간이, 현재 진행중인 회의시간에 침범(?), 영향을 주지 않기 때문이죠. 회의시간 간에 중복이 없다는 말입니다 !

 

아이디어는 다음과 같습니다. 

일단 다음 회의로 들어갈 수 있는 조건은, 현재 진행중인 회의 진행시간에 영향을 주지 않는다는 것입니다. 그말은 즉, 현재 진행중인 회의의 종료시간의 값보다 같거나, 커야 합니다. 작게되면, 영향을 주겠죠 ?

그래서 입력받은 회의의 시간을 검사하면서 만약, 시작시간이 현재 진행중인 회의의 종료시간보다 크거나 같다면 다음 회의로 넣을 수 있습니다. 

 

하지만! 이렇게 입력받은 그대로 검사를 하게되면 조건을 만족하긴 하지만, 그 개수가 최대가 되진 않습니다.

예를 들어서 현재 회의의 시간은 [ 1,4 ]이고 그 다음 회의 시간이 [ 4,10 ] , [5,6], [ 6,7]이라면 [ 4,10 ]은 조건을 만족합니다. 하지만 [ 4,10 ]이 들어가면 뒤의 [5,6], [ 6,7]회의들이 못들어 갑니다. 결국엔 회의 1개만 추가되는 거죠.

 반대로 [5,6], [ 6,7]이 들어가게 되면 뒤의 [ 4,10 ]은 못들어 가지만 [5,6], [ 6,7] 즉 2개의 회의가 추가되는 거죠. 문제에서 최대한 많은 회의를 넣으라고 했습니다.

 

해결방법은

입력받은 회의들을 종료시간을 기준으로 오름차순 정렬 하는 것입니다.

[ 1, 4 ] [ 4, 10 ] [ 5,6 ] [ 6,7 ]회의가 있다면, 현재 상태의 최대 회의수는 2개 입니다.

하지만 종료시간을 기준으로 정렬하면 [ 1,4 ]  [ 5,6 ] [ 6,7 ] [ 4, 10 ]이 되고, 최대 3개의 회의를 넣을 수 있습니다.  여기서 중요한 점은, 정렬을 할 때, 만약 종료시간이 같으면 시작시간이 큰 값을 기준으로 정렬합니다.

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        ArrayList<Conference> list = new ArrayList<Conference>();

        for (int i = 0; i < n; i++) {
            list.add(new Conference(sc.nextInt(), sc.nextInt()));
        }

        Collections.sort(list, new Comparator<Conference>() {
            public int compare(Conference c1, Conference c2) {
                if (c1.getEnd() > c2.getEnd()) {
                    return 1;
                } else if (c1.getEnd() < c2.getEnd()) {
                    return -1;
                }
                return c1.getStart() - c1.getEnd();

            }
        });

        int end = -1;
        int start;
        int count = 0;

        for (int j = 0; j < n; j++) {
            start = list.get(j).getStart();

            if (start >= end) {
                end = list.get(j).getEnd();
                count++;
            }
        }
        System.out.println(count);
    }
}

class Conference {
    int start;
    int end;

    Conference(int start, int end) {
        this.start = start;
        this.end = end;
    }

    public int getStart() {
        return this.start;
    }

    public int getEnd() {
        return this.end;
    }
}

1. 입력받은 시작/종료시간을 가지는 Conference객체를 만들고, list에 추가해 줍니다.

2. list에는 각각의 회의가 저장되어 있고, 이를 종료시간을 기준으로 정렬해줍니다.

3. 마지막으로 list에서 회의정보를 하나씩 꺼내와서 현재 진행중인 회의 종료시간보다 꺼내온 회의의 시작시간이 같거나 크다면 count를 하나 올려줍니다. 여기서 특이한건 처음 end=1라는 점인데, 이는 가장 첫번째 회의를 무조건 count해주기 위해서 입니다. 각각의 시간은 무조건 자연수이기 때문에, 마이너스 값을 가질 수 없고, end=-1일 때, for문의 첫번째 조건에서 무조건 count를 하게 됩니다.

 

이런 방법이 싫다면, end를 첫번째 회의의 종료시간으로 초기화하고 count=1로 시작하면 됩니다. 대신 두번째 회의부터 검사해야 겠죠 ?