[BOJ]11000号教室(java)の割り当て


質問する


11000号:教室の手配

に答える


優先キューの使用
優先順位Qとは?データ構造は、まず、入力された順序でデータをパブリッシュするのではなく、データの優先度を決定し、次に優先度の高い領域を決定します.
問題では、カリキュラムが最も早く終了した教室(PriorityQueue Default)を優先的に手配する必要があります.
カリキュラムのstartとendをint[]に入力して保存します.終了時間順に昇順に並べ替えます.まず最初の要素のendTimeをキューに入れ、繰り返し文の実行時間が現在最も早く終了した教室時間(time.peek()が比較した教室開始時間(教室[i][0])より大きい場合は、授業を継続することができる.この場合、教室のendTimeを再設定する必要があるため、ポーリング後に最終結果値キューの寸法出力を再提供します.

コード#コード#

import java.util.*;
import java.io.*;

public class Main{
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] lectures = new int[N][2];
		for(int i =0 ; i< N ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			lectures[i][0] = Integer.parseInt(st.nextToken());
			lectures[i][1] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(lectures, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0] == o2[0]) return o1[1] - o2[1];
				return o1[0] - o2[0];
			}
		});
		PriorityQueue<Integer> time = new PriorityQueue<>();
		time.offer(lectures[0][1]);
		for(int i = 1; i<lectures.length ; i++) {
			if(time.peek() <= lectures[i][0]) time.poll();
			time.offer(lectures[i][1]);
		}
		System.out.println(time.size());
	}
}