백준 1931번: 회의실배정

백준 1931번: 회의실배정

 

 

- 최대한 많은 회의를 배정하기 위해서는 빨리 끝나는 회의를 우선배치해야 됩니다.

- 왜 빨리 끝나는 회의 순서로 배치해야 되는지 증명을 여기서 하면 좋겠지만 이미 깔끔하게 설명한 유튜브 동영상이 있어서 첨부합니다. (강의실 배정 알고리즘 증명 유튜브 동영상)

 

- Comparator 를 통해 회의가 빨리 끝나는 순서대로 정렬합니다.

- 앞의 회의가 끝나는 시간보다 회의를 시작하려는 시간이 크거나 같으면 회의를 하고  ANSWER++ 를 합니다. 이 작업을 a[1]부터 a[N-1]까지 반복합니다.

- 최소 한 개의 회의는 항상 할 수 있으므로 ANSWER은 1로 초기화합니다.

 

	import java.util.*;
	class room{
	int start;
	int end;
	public room(int start, int end){
	this.start = start;
	this.end = end;
	}
	public static Comparator<room> comparator = new Comparator<room>() {
	@Override
	public int compare(room o1, room o2) {
	if(o1.end == o2.end)
	return Integer.compare(o1.start, o2.start);
	else
	return Integer.compare(o1.end, o2.end);
	}
	};
	}
	public class Main {
	static int N;
	static int ANSWER = 1;
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	N = sc.nextInt();
	room[] a = new room[N];
	for(int i = 0; i < N; i++){
	a[i] = new room(sc.nextInt(), sc.nextInt());
	}
	Arrays.sort(a, room.comparator);
	int tmp = a[0].end;
	for(int i = 1; i < N; i++){
	if(a[i].start >= tmp){
	tmp = a[i].end;
	ANSWER++;
	}
	}
	System.out.println(ANSWER);
	}
	}

view raw BOJ_1931.java hosted with ❤ by GitHub