백준 1931번 회의실 배정 (Java)

 

해결 과정

회의실 배정을 적절히 해서 가장 많은 스케줄을 할당하게 하는 문제다. 처음에는 솔루션이 떠오르지 않아, 모든 케이스에 대해서 다음에 올 가장 적절한 스케줄을 찾아나가는 식의 Brute Force를 생각해봤으나, 회의의 수가 최대 100000개이기 때문에 모든 케이스에 대해서 접근하면 O(n^2), 즉, 100000^2의 연산이 필요하다. 따라서, 시간초과가 발생할 여지가 충분했다.

 

따라서 적어도 O(n*lgN)이나 O(n)의 시간복잡도를 가지는 알고리즘이 필요했는데, 시작 시간이나 종료 시간을 기준으로 해당 타임에 가장 적합한 스케줄을 앞에서부터 찾아나가면 되겠다고 접근했다.

 

문제를 자세히 보면, 종료 시간이 가장 짧은 스케줄들을 차례대로 이어나가다보면 회의의 최대 개수를 구할 수 있음을 알 수 있다. 하지만 단순히 종료 시간이 가장 짧은 스케줄을 찾고 다음 시작 시간을 설정하는 식으로 반복하다보면, 종료 시간이 가장 짧은 스케줄을 찾기 위해 모든 스케줄을 다시 loop해야함을 알 수 있다. 따라서, 이러한 문제를 해결하기 위해 정렬을 이용했다.

 

가장 빠른 종료 시간을 기준으로 정렬한다면 정렬한 List를 순회하면서 회의의 개수를 추적해나갈 수 있다. 정렬은 여러 방법으로 구현이 가능하지만, 문제 해결 과정에서 시작 시간과 종료 시간을 담은 객체를 생성했기 때문에 이를 정렬할 수 있는 Comparable 인터페이스를 구현하도록 했고, Collection.sort() API를 사용했다.

 

단, 일부 테스트 케이스에서 실패했는데, 종료 시간이 같은 경우 시작 시간이 빠른 스케줄이 먼저 와야된다.

예를 들어, [4 8]과 [8 8]이 있으면 문제의 조건에 의해, 4 8과 8 8 두번의 스케줄을 할당할 수 있지만, [8 8]이 리스트에 먼저 들어온다면[8 8]하나만 선택하고 8 이후의 스케줄을 찾게 될 것이다. 따라서 한번만 스케줄을 할당하는 오류를 만든다.

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    static class Schedule implements Comparable<Schedule>{
        int start;
        int end;

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

        @Override
        public int compareTo(Schedule o) {
            if (this.end > o.end) {
                return 1;
            }
            else if (this.end == o.end) {
                if (this.start > o.start) {
                    return 1;
                }
            }

            return -1;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        ArrayList<Schedule> scheduleArrayList = new ArrayList<>();

        for (int i=0; i<n; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();

            scheduleArrayList.add(new Schedule(start, end));
        }

        Collections.sort(scheduleArrayList);

        int time = 0;
        int count = 0;

        for (Schedule schedule: scheduleArrayList) {
            if (schedule.start >= time) {
                count++;
                time = schedule.end;
            }
        }

        System.out.println(count);
    }
}