[백준] 1931 회의실 배정

1931번: 회의실 배정 (acmicpc.net)

1931번: 회의실 배정

문제

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

 

 

내풀이

회의실 배정은 알고리즘 수업을 들을 때 예제로 나올 정도로 그리디 알고리즘의 대표적인 문제

그리디 알고리즘을 알기 전에 0/1 knapsack과 비슷하게 가성비(?) 등의 그럴듯한 생각의 함정에 빠지기 쉬웠다.

끝나는 시간 순으로 정렬하고 순서대로 되는대로 회의실을 배정하면 최대한 많이 집을 수 있음

왜냐하면 가장 적은 시간 내에 회의실 하나를 배정하는 것이 최적의 해결인데 

위의 예시를 봤을 때 10 이전에 최대한 빨리 회의실을 하나 배정하는 방법은? => 최대한 회의 종료시간이 빠른 회의를 선택하는 것이다. 즉 회의 시간을 최소화하는 것이 아닌 전체 시간(회의를 위해 기다리는 중간 비는시간 포함)을 최소화하는 기준으로 생각하는 것이다.

이걸 하나의 subProblem으로 (1,4)를 배정하고, 4 이후의 범위에서 subProblem을 해결하면 (5,7) 을 선택하게 될 것이다. 이렇게 subProblem 들을 최적의 방법으로 해결하여 합치면 처음에 구하려고 했던 답에 도달하게 된다.

 

위의 방법을 구현한 방법은 

우선 회의 시간이 끝나는 시간이 빠른순, 같다면 시작시간이 더 빠른순으로 정렬한 후, Greedy 하게 되는대로 선택하며 선택한 회의의 숫자를 세었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static String src="11\r\n"
			+ "1 4\r\n"
			+ "3 5\r\n"
			+ "0 6\r\n"
			+ "5 7\r\n"
			+ "3 8\r\n"
			+ "5 9\r\n"
			+ "6 10\r\n"
			+ "8 11\r\n"
			+ "12 12\r\n"
			+ "8 12\r\n"
			+ "12 14";
	
	static int n;
	static int result=0;
	
	public static void main(String arg[]) throws IOException {
		//input= new BufferedReader(new InputStreamReader(System.in));
		input= new BufferedReader(new StringReader(src));
		
		n=Integer.parseInt(input.readLine());
		StringTokenizer str;
		
		int[][] data=new int[n][2];
		
		for(int i=0;i<n;i++) {
			str=new StringTokenizer(input.readLine());
			data[i][0]=Integer.parseInt(str.nextToken());
			data[i][1]=Integer.parseInt(str.nextToken());
		}
		
		quickSort(data);
		
//		for(int i=0;i<n;i++) {
//			System.out.println(Arrays.toString(data[i]));
//		}
		
		
		find(data,0,0);
		System.out.print(result);
		
	}
	//회의실 선택하는 메소드, 끝나는 시간 오름차순으로 정렬되있기에 greedy하게 선택함
	public static void find(int[][] data,int start,int index) {
		if(index>=n) { //범위 벗어나면 리턴으로 끝내줌
			return;
		}
		if(start<=data[index][0]) { //회의 시작 시간이 허락만해주면 바로 집음 
			start=data[index][1];
			result++;
		}
		find(data,start,index+1);
	}
	
	//퀵소트 메소드 구현 부분
	public static void quickSort(int[][] arr) {
        sort(arr, 0, arr.length - 1);
    }

    public static void sort(int[][] arr, int low, int high) {
        if (low >= high) return;

        int mid = partition(arr, low, high);
        sort(arr, low, mid - 1);
        sort(arr, mid, high);
    }

    public static int partition(int[][] arr, int low, int high) {
        int pivot = arr[(low + high) / 2][1];
        while (low <= high) {
            while (arr[low][1] < pivot) 
            	low++;
            while (arr[high][1] > pivot) 
            	high--;
            if (low <= high) {
                swap(arr, low, high);
                low++;
                high--;
            }
        }
        return low;
    }
    //스왑부분을 조정함으로서 원하는대로 (회의 시간이 끝나는 시간이 빠른순, 같다면 시작시간이 더 빠른순) 정렬
    public static void swap(int[][] arr, int i, int j) {
        int tmp = arr[i][1];
        arr[i][1] = arr[j][1];
        arr[j][1] = tmp;
        
      //끝부분 숫자가 같은데 이미 시작부분 숫자도 정렬되있는 경우에는 스왑안함
        if(arr[i][1] == arr[j][1]&&arr[i][0] < arr[j][0]) { 
        }else {
        	tmp = arr[i][0];
            arr[i][0] = arr[j][0];
            arr[j][0] = tmp;
        }
        
    }
	
	
}