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

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

1931번: 회의실 배정

---

동작 설명

각각의 회의 정보를 입력받는다

입력받은 회의들을 끝나는시간을 기준으로 오름차순 정렬한다.

 

d[]라는 배열을 하나 만들어서

d[i] 에는 i시간까지 수행가능한 최대 회의 개수를 저장할 수 있도록 했다.

 

이제 각각의 회의들을 순회하면서 d[]배열을 채우면 된다.

d[i]는 d[i-1]로 일단 값을 갱신한다

(i시간에는 당연히 i-1시간보다 더 많은 회의를 수행하거나, 같은 수의 회의를 수행할 것이니까)

그리고 i시간에 끝나는 회의를 찾는다.

d[해당회의 시작시간]+1한 값과 현재 d[i]값을 비교해서, 더 큰 값으로 갱신한다.

 

+

i-1인덱스를 사용해야 하기 때문에 반복은 인덱스1부터 시작하고,

인덱스0에 해당하는 부분은 따로 작성했다.

 

+

회의가 시작하자마자 끝나는

것(0-0 1-1 2-2 등등)은 바로 d[i]값을 1증가시키도록 했다.

---

코드

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

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n=Integer.parseInt(br.readLine());
		int[] d;
		int[][] arr = new int[n][2];
		
		for(int i=0;i<n;i++) {
			st= new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end= Integer.parseInt(st.nextToken());
			arr[i][0]=start;
			arr[i][1]=end;
		}
		
		//끝나는시간 기준으로 정렬
		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];
				}
			}
		});
		
		d=new int[arr[n-1][1]+1];
		d[0]=0;
	
		int idx=0;
		while(idx<n&&arr[idx][1]==0) {
			d[0]++;
			idx++;
		}
		for(int i=1;i<=arr[n-1][1];i++) {
			d[i]=d[i-1];
			while(idx<n&&arr[idx][1] <= i) {
				if(arr[idx][0]==arr[idx][1]) {
					d[arr[idx][0]]++;
				}
				else if(d[arr[idx][0]]+1>d[i]) {
					d[i]=d[arr[idx][0]]+1;
				}
				
				idx++;
				
			}
			
		}

		System.out.println(d[arr[n-1][1]]);
	}

}

 

-이차원배열에서 [][1] 기준으로 정렬하기

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];
				}
			}
		});