백준 1931 회의실배정

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

활동 선택 문제 유형의 대표 문제이다

그리디에 대한 확실한 준비는

https://jackpot53.tistory.com/category/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%28Algorithm%29/%EA%B7%B8%EB%A6%AC%EB%94%94%28Greedy%29

여기서 유형을 익히고 하면 어느정도 일정수준으로 올라올것으로 보인다..

아무튼 이러한 배정문제에서 중요한건

정렬 그리고 선택이다..

그래서 끝나는 시간 순으로 정렬을하고 빨리시작하는걸 골라야된다

why?

따로따로보면 안되고

끝나는 시간이 빠르고 => 그 빠른순서 다음에 올 시작시간을 고른다 = >

이렇게 연계? 되서 그리디한 생각을 해야되는것 같다..

그래서 이걸 바탕으로 구현코드는 다음과같다

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

class room implements Comparable<room>{
	long s;
	long e;
	
	public room(long s, long e) {
		this.s= s;
		this.e=e;
	}
	
	public int compareTo(room o) {
		
		if(this.e>o.e) {
			return 1;
		}
		else if(this.e==o.e) {
			if(this.s<o.s) {
				return 1;
			}
		}
		return -1;
	}
	
	
}

public class 회의실배정 {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());
		
		PriorityQueue<room> pq = new PriorityQueue<>();
		for(int i=0;i<tc;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			long s = Long.parseLong(st.nextToken());
			long e = Long.parseLong(st.nextToken());
			
			pq.add(new room(s,e));
		}
		int count = 0 ;
		
		long end = 0;
	
		
		while(!pq.isEmpty()) {
			room cur = pq.poll();
			System.out.println(end + " : " + cur.s + " " + cur.e );
			
			if(end <=cur.s) {
				count++;
				end = cur.e;
			}
		}
		System.out.println(count);
		
	}

}

ㅋㅋㅋㅋㅋㅋㅋ 수많은 실패

초기에는 생각을 총 시간이 짧고 빨리시작하는걸 골라버리고 그다음에 구분해서 선택하면안되나싶엇는데

그러면 길이가 짧은것들이 뒤에 쏠리고 앞에를 아에 선택을 안해버릴수도있어서 안된다..

아무튼 골드 5 ㄱㄱ