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

 

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

1931번: 회의실 배정

 

문제

 

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

 

입력

 

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

 

출력

 

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

 

 

 

풀이 방법

 

한번에 풀기에는 어려운 문제였다.
이차 이상의 for문을 사용하면 시간초과를 일으키기에 일차 식의 for문을 이용해야 했고,
그러기 위해서는 정렬을 이용해야 했다.
이러한 아이디어를 위해서 2개의 매개변수 비교를 위한 Comparator를 사용하였다.
시작시간과 관계없이 종료시간을 기준으로 정렬하면 다음번의 회의 시작시간을 일찍 시작할 수 있고
그만큼 회의를 많이 진행할 수 있다. 만약 종료시간이 같은 경우라면 시작시간이 짧을수록 좋다.

 

 

작성 코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

package greedy;   import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer;   public class BJ_1931 {       static int N;     static int arr[][];     static boolean visited[][];       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));           N = Integer.parseInt(br.readLine());         arr = new int[N][2];         visited = new boolean[N][2];           for (int i = 0; i < N; i++) {             StringTokenizer 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[]>() {               @Override             public int compare(int[] o1, int[] o2) {                 if (o1[1] > o2[1]) { // 종료시간을 기준으로 오름차순                     return 1;                 } else if (o1[1] == o2[1]) { // 종료시간이 같을 경우                     if (o1[0] > o2[0]) {                         return 1; // 시작 시간을 기준으로 오름차순                     }                 }                 return -1;             }         });           int first = arr[0][1];         int count = 1;           for (int i = 1; i < N; i++) {             if (arr[i][0] >= first) {                 first = arr[i][1];                 count++;             }         }           System.out.println(count);     }   }