[백준 - 11000] 골드5 - 강의실 배정

www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

1. 유형

그리디, 커스텀 정렬

 

2. 풀이

시작 시간 기준 오르차순 정렬을 한다.

 

우선순위큐에 처음 값을 넣고나서 끝나는 시간보다 현재 시작시간이 같거나 크면,

 

큐에 넣어주는 식으로 고친다.

 

3. 풀이

package 그리디;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class back_11000강의실_배정 {
	static class Pair implements Comparable<Pair>{
		int a;
		int b;
		public Pair(int a, int b) {
			this.a=a;
			this.b=b;
		}
		@Override
		public int compareTo(Pair o) {
			// TODO Auto-generated method stub
			return this.b - o.b;
		}
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int time[][] = new int[n][2];
		for (int i = 0; i < time.length; i++) {
			time[i][0]= sc.nextInt();
			time[i][1]= sc.nextInt();
		}
		Arrays.sort(time, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});
		//우선순위큐 선언 끝나는 시간 오름차순 정렬
		PriorityQueue<Pair> pq = new PriorityQueue<>();
		//time만큼 반복
		pq.add(new Pair(time[0][0],time[0][1]));
		for (int i = 1; i < time.length; i++) {
			Pair last = pq.peek();
			//큐의 끝값보다 time의 시작값이 더 크다면 poll하고 넣기
			if(last.b <= time[i][0]) {
				pq.poll();
			}
			pq.add(new Pair(time[i][0], time[i][1]));
		}
		System.out.println(pq.size());
	}
}