[JO]1828号:冷蔵庫(Java)

1701 ワード
グリディ テキストリンク

質問する


JUNGOL 1828  

に答える


冷蔵庫の化学物質が最大値に達しなければならないため、「階調」アルゴリズムを適用します.
化学物質の最低および最高の貯蔵温度を格納する材料カテゴリを宣言する
最大値から昇順に並べ替えることができるように、MaterialクラスでCompareableを実装します.
昇順で並べ替えた後、Maxを最初の要素の最大値として保存します.
mat[i]の最小値が現在の最大値より大きい場合、同時に保存できないため、cnt+1後.
最大値を要素の最大値にリセット
(最大値で昇順ソートされているため、次の要素の最大値は前の最大値より小さくできません)

コード#コード#

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

public class Main {
	static class Material implements Comparable<Material>{
		int min, max;
		public Material(int min, int max) {
			super();
			this.min = min;
			this.max = max;
		}
		@Override
		public int compareTo(Material o) {
			int val = this.max - o.max;
			if(val != 0) return val;
			
			return this.min - o.min;
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Material[] mat = new Material[n];
		for(int i =0 ; i< n ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			mat[i] = new Material(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		Arrays.sort(mat);
		int max = 0;
		int cnt = 1;
		for(int i =1 ; i < mat.length ; i++) {
			if(max<mat[i].min) {
				cnt++;
				max = mat[i].max;
			}
		}
		System.out.println(cnt);
	}
}
[BOJ]1992号:四叉木(Java)
[BOJ]2961号:道英が作ったグルメ(Java)