[그리디 #4] 백준 1931번: 회의실배정 JAVA

1931번: 회의실 배정

문제

---

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

 

입력

---

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

 

출력

---

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

 

예제입출력

---

예제 입력	예제 출력
11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14	4

 

풀이

---

 이 문제는 생각보다 풀이가 쉽게 떠오르지 않았다... 각 회의마다 걸리는 시간의 최소값 접근하려 하니깐 로직만 복잡해지고 직감적으로 반례가 존재할 것같은 생각이 들었다. 이 유형은 그리디 알고리즘의 대표적인 문제중 하나라고 한다.

 

 이 문제는 시간차의 최소값으로 접근하는 것이 아닌 서로 겹치지 않은 회의에 대해 종료시간이 빠르면 더 많은 회의를 선택할 수 있는 경우가 많아진다는 것에 초점을 맞추면 쉽게 풀린다.

 

자세한 풀이:[백준] 1931번 : 회의실배정 - JAVA [자바] (tistory.com) 

 

 

 

코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		int[][] time = new int[n][2];
		
		StringTokenizer st;
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			time[i][0] = Integer.parseInt(st.nextToken());
			time[i][1] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(time, new Comparator<int[]>() {
			
			public int compare(int[] o1, int[] o2) {
				if(o1[1] == o2[1]) {
					return o1[0] - o2[1];
				}
				
				return o1[1] - o2[1];
			}
		});
		
		int count = 0;
		int preEndtime = 0;
		
		for(int i=0; i<n; i++) {
			if(preEndtime <= time[i][0]) {
				preEndtime = time[i][1];
				count++;
			}
		}
		
		bw.write(String.valueOf(count));
		bw.flush();
		bw.close();
	}
}