[白俊]1931号:会議室の手配


質問する



に感銘を与える


2 D配列を宣言して入力データ構造を作成します.BufferedReaderを使用して、for文として複数の値を最初に受け入れます.オブジェクトをソートする場合、Comparatorインタフェースをカスタマイズできるcompare()抽象メソッドが上書きされ、終了時間順に昇順にソートされます.
cf.BufferedReaderは一度だけ宣言します.for文のbr変数のメソッドreadLine()は、入力値を引き続き受け入れることができます.
しかし、問題はその後です.終了時間<開始時間では、最小終了時間を求めるのは難しい.1回目のソートとその後の比較では,この過程を1回繰り返すかどうか悩んだが,この部分は終始解けず助けられた(https://st-lab.tistory.com/145).
必要なのは終了時間の変化で更新することです.
ソートされた時間は十分に活用する必要がありますが、終了した時間は迅速な順序でソートされるので、既存の終了時間に比べて開始時間が重複しないことが重要です.
したがって、開始時間が終了時間以上であれば、次の会議の時間になります.そして次の会議の終了時間を終了時間変数に代入し、すぐに更新します.最初から最後までこの繰り返しです.
これはグリディアルゴリズムを用いた問題であり,一瞬ごとに最適と考えられる場合を選択することによって最終値を求める.

に答える

package december_first;

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

public class baek_1931_3 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int[][] arr = new int[N][2];
		
		// arr에 입력 값 넣어주기
		// 여러 값을 배열에 넣어줄 때 콘솔로 출력되는 무언가가 있으면 안 됨(흐름 끊기면 에러남)
	    for (int i = 0; i < N; i++) {
	    	
	    	// br.readLine() 쓸 때 오류 처리 꼭 해주기
	    	StringTokenizer st = new StringTokenizer(br.readLine()," ");  //br.readLine() 오류 처리
	    	
	    	for(int j = 0; j < 2; j++) {
	    		
	    		// StringTokenizer는 String을 쪼갤 때 사용함 -> Integer.parseInt() 이용해야
	    		// Integer.valueOf(str)은 먹히지 않음
	    		arr[i][j] = 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];
				}
                
                // 1 3
                // 8 8
                // 4 8
                -> 마지막 두 가지의 순서 바꿔줘야 최대 회의 개수 구할 수 있음
					
				return o1[1] - o2[1]; 
				// 두번째 원소들끼리 비교 arr[0][1] vs. arr[1][1]
				// 오름차순으로 정렬 (양수이면 순서 바꿈)
			}
			
		});
	    
		int count = 0;
		int endTime = 0;
	 	
	 	for(int i = 0; i < N; i++) {
	 		
	 		// 종료시간이 다음 회의 시작시간보다 작거나 같으면
	 		if(endTime <= arr[i][0]) {
	 			
	 			// 종료시간을 해당 회의 종료시간으로 갱신
	 			endTime = arr[i][1];
	 			count++;
	 		}
	 		
	 	}
	 	
	 	System.out.println(count);
	 	
	 	
	}

}

References


「質問の回答」を参照してください.
https://st-lab.tistory.com/145
ComparableとComparatorについて
https://st-lab.tistory.com/243
2 D位置合わせを使用する座標位置合わせの問題
https://st-lab.tistory.com/110#%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
br.readLine()とst.nextToken()をintのIntegerに変換します.parseInt()
https://makemethink.tistory.com/171