[백준 알고리즘] 1931번 자바(Java) 회의실 배정

조건

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2의 31승-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

풀이

주어진 입력을 보면 일단 시간의 최대가 2^31 -1이므로 int형으로 표현가능하다. 그리고

회의수가 10만인것을 보니 O(n^2)으로는 풀면 안되고 O(n)또는 O(nlogn)으로 풀어야하는것을 알 수있다. 

이것을 바탕으로 문제를 읽어봤다. 결국은 시작시간보다 종료시간이 중요하고 회의가 끝날때마다

다음 회의를 찾는 요소중 제일 중요한건 빠른 종료시간이다. 그 후에 시작시간이 조건을 충족하는지 보면된다.

그래서 봐야되는 순서는 종료시간->시작시간이 된다

 

그럼 이제 시작시간과 종료시간이 들어간, 2단배열로 이루어진 회의를 정렬할려면 Comparator 인터페이스를 써야한다.

사실은 우선순위큐(힙)을 사용하는 방법도 있지만 더 단순하게 Comparator인터페이스 내 compare메서드가 사용하기 더 편리해서 그 방법으로 풀어봤다. 종료시간이 같은경우에만 시작시간이 빠른 회의를 찾는 식으로 메서드를 바꿔서 사용했다. 

 

 

 

예제 입력 예시

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

 

예제 출력 예시

4

소스코드

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

//1931번
//끝나는 시간을 기준으로 풀어보기

public 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[][] meeting = new int[N][2];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            meeting[i][0] = Integer.parseInt(st.nextToken());
            meeting[i][1] = Integer.parseInt(st.nextToken());
        }
        int ans = 0;   //회의 개수
        Arrays.sort(meeting, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1]==o2[1]) return o1[0] - o2[0]; //종료시간 같은 경우만 시작시간 비교
                return o1[1] - o2[1];
            }
        });
        int time = 0;  //현재 시간
        for (int i = 0; i < N; i++) {
            if(meeting[i][0]>=time){
                ans++;
                time = meeting[i][1];
            }
        }
        System.out.println(ans);
    }
}

 

 

 

 

문제 출처

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

1931번: 회의실 배정