백준 1931번 - 회의실 배정

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

1931번: 회의실 배정

 

 

 

 

 

 

이전에 한 번 푼 적이 있어서 풀이법을 떠올리는 건 쉬웠다.

 

1.정렬 : 우선 끝나는 시간을 기준으로 오름차순 정렬을 하고, 끝나는 시간이 같은 경우에는 시작 시간을 기준으로 오름차순 정렬을 한다.

2. 모든 시간에 대해서 끝나는 시간을 기준으로 하여 가능한 다음 회의 시작 시간을 찾는다. 

 

 

2차원 배열을 정렬하는데, Arrays.sort와 Comparator 사용이 아직 미숙하다.

 

 

 

코드

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 Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[][] arr = new int[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 o1[0] - o2[0]; //시작 시간 오름 차순
				}else {
					return o1[1] - o2[1]; //끝나는 시간 오름 차순
				}	
			}
		});

		int count = 0;
		int end = 0; //끝나는 시간이 기준
		for(int i = 0; i < N; i++) {
			if(arr[i][0] >= end) {
				count++;
				end = arr[i][1];
			}
		}
		
		System.out.println(count);
	}

}

 

 

 

 

 

 

결과