[Java/정올/탐욕법(그리디, Greedy)] 1828번: 냉장고

문제

www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=99&sfl=wr_hit&stx=1828

JUNGOL

 

문제 이해에 시간이 많이 걸렸다.

처음엔 그리디인 걸 알아도 안겹치게 하는 줄 알고 어리버리 했었다...

 

냉장고의 최소 개수이기 때문에,

처음 잡은 화학물질의 최고 온도보다 다음 화학물질의 최저 온도가 낮은 경우(겹치는 경우) 냉장고를 함께 써도 된다.

아니라면 새로운 냉장고를 추가해준다.

 

 

 

코드

Comparable을 구현하는 김에 PriorityQueue를 이용했는데,

다른 사람들 코드를 보니까 그냥 int[][] 배열을 써도 될 것 같다.

 

package jungol;

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

public class JUNGOL1828 {
	static PriorityQueue<Refrigerator> pq = new PriorityQueue<Refrigerator>();

	static class Refrigerator implements Comparable<Refrigerator> {
		int low;
		int high;

		public Refrigerator(int low, int high) {
			super();
			this.low = low;
			this.high = high;
		}

		@Override
		public int compareTo(Refrigerator refri) {
			int diff = this.high - refri.high;
			return diff != 0 ? diff : this.low - refri.low;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		for (int i = 0; i < n; i++) {
			String[] chemicals = br.readLine().split("\\s");
			pq.offer(new Refrigerator(Integer.parseInt(chemicals[0]), Integer.parseInt(chemicals[1])));
		}
		
		getRefrigerator();
		br.close();
	}

	private static void getRefrigerator() {
		int cnt = 1;
		int big = pq.poll().high;
		int size = pq.size();

		int j = 0;
		for (int i = 0; i < size; i++) {
			if (big >= pq.peek().low) {
				pq.poll();
				j++;
			} else {
				big = pq.poll().high;
				++cnt;
			}
		}
		
		System.out.println(cnt);
	}

}