[백준] 1931번 : 회의실 배정 (JAVA)

그리디 알고리즘 관련 문제인 11047번 : 동전 0 을 풀고

다음으로 1931번 : 회의실 배정 문제를 풀었다.

 

그리디 알고리즘에 대해 아직 이해하지 못했다면 다음의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/12

[알고리즘] 그리디 알고리즘 (Greedy Algorithm)

 

 

바로 앞 문제인 11047번 : 동전 0에 대한 내용은 바로 앞의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/15

[백준] 11047번 : 동전 0 (JAVA)

 

---

<문제>

 

<문제 해석>

그리디 알고리즘을 이용하여 각 회의가 겹치지 않게 하면서 사용할 수 있는 회의실의 최대 갯수를 구하라.

 

 

<문제 해결>

이번 문제는 바로 이전 문제인 "동전 0 " 보다는 어려웠다.

하지만 그리디 알고리즘을 이용하여 간단하게 풀 수 있었다.

 

이 문제의 핵심은 회의의 종료 시간이다.

 

회의의 시작시간이 같아도 종료시간이 더 빠른 것을 골라야한다.

서로 겹치지 않는 활동에 대해 종료시간이 빠르면 더 많은 활동을 선택할 수 있는 시간이 많아진다는 것이다.

 

결국 종료 시간으로 정렬 후, 빨리 끝나는 것을 선택해야한다.

*정렬할 때, 종료시간이 같을 경우 시작시간이 빠른 순으로 정렬해야 한다.*

 

 

<알고리즘>

1. 회의의 시작시간, 종료시간을 종료시간으로 정렬한다.

    (종료시간이 같을 경우, 시작시간이 빠른 순으로 정렬해야한다.)

 

2. 현재 회의의 종료 시간이 다음 회의의 시작시간보다 작거나 같으면

 

3. 현재 회의의 종료 시간을 다음 회의의 종료시간으로 바꾸고

 

4. 회의실 갯수 + 1

 

 

<코드>

import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {	

	static int n;
	static int[][] ar;
	static int count;
	
	public static void main(String[] args) throws IOException {
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		ar = new int[n][2];
		for(int i=0;i<n;i++) {
			ar[i][0] = sc.nextInt();
			ar[i][1] = sc.nextInt();
		}
		
		sort();
		cal();
		
		System.out.println(count);

	}
	
    
	static void sort() {
		Arrays.sort(ar,new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[1] == o2[1]) {
					return o1[0] - o2[0];
				}
				return o1[1] - o2[1];
			}
			
		});
	}
	
    
	static void cal() {
		count = 0;
		int time = 0;
		
		for(int i=0;i<n;i++) {
			if(time <= ar[i][0]) {
				time = ar[i][1];
				count++;
			}
		}
		
	}
}

 

 

---

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

1931번: 회의실 배정