[백준 1931] 회의실배정 - 자바

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

1931번: 회의실배정

 

1. 풀이

---

종만북에도 나오는 그리디 알고리즘의 개념을 이해하는데 도움을 주는 문제입니다.

 

문제의 목표는 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾기 입니다.

 

조건은 아래와 같습니다.

 

1. 회의가 한번 시작하면 중간에 중단 될 수 없습니다.

 

2. 한 회의가 끝나는 동시에 다음 회의가 시작될 수 있습니다.

 

3. 회의의 시작 시간과 종료시간이 같을 수도 있습니다. ( 시작하자마자 끝났다고 간주 )

 

이 문제를 시각화하면 아래와 같습니다.

 

시각화

회의가 일찍 끝나는 기준으로 그리디를 전개하면 사용할 수 있는 최대의 회의 개수를 얻을 수 있습니다.

 

정렬할때 중요한 것은 끝나는 기준으로 오름차순으로 정렬하되, 끝나는 시간이 같으면 시작하는 시간을 기준으로 오름차순 해야합니다.

 

2. 코드

---

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int[][] times = new int[n][2]; 
		
		for(int i = 0; i < n; i++) {
			times[i][0] = sc.nextInt();
			times[i][1] = sc.nextInt();
		}
		
		// 정렬 ( 끝나는 시간으로 정렬하되, 같을시 시작시간으로 정렬 )
		Arrays.sort(times, new Comparator<int []>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[1] == o2[1])
					return Integer.compare(o1[0], o2[0]);

				return Integer.compare(o1[1], o2[1]);				
			}
		});
		
		int result = 0;
		int tmp = 0;
		for(int i = 0; i < n; i++) {
			if(tmp <= times[i][0]) {
				result++;
				tmp = times[i][1];
			}
		}
		
		System.out.println(result);
		
		
		sc.close();
		return;
	}
}