<백준 알고리즘> 1931번: 회의실 배정

문제

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

입력

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

출력

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

예제 입력 1

11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14

예제 출력 1

4

힌트

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

---

Solution

#include<stdio.h>
#include<stdlib.h>

int stemp[100000], etemp[100000];

void merge(int *start,int *end,int left,int right,int mid)
{
	int i=left, j=mid+1;

	for(int k=left;k<=right;k++)
		if(j>right)
		{
			stemp[k]=start[i];
			etemp[k]=end[i];
			i++;
		}
		else if(i>mid)
		{
			stemp[k]=start[j];
			etemp[k]=end[j];
			j++;
		}
		else if(end[i]<end[j] || end[i]==end[j] && start[i]<start[j])
		{
			stemp[k]=start[i];
			etemp[k]=end[i];
			i++;
		}
		else
		{
			stemp[k]=start[j];
			etemp[k]=end[j];
			j++;
		}

	for(int k=left;k<=right;k++)
	{
		start[k]=stemp[k];
		end[k]=etemp[k];
	}
}

void mergesort(int *start,int *end,int left,int right)
{
	if(left<right)
	{
		int mid=(left+right)/2;
		mergesort(start,end,left,mid);
		mergesort(start,end,mid+1,right);
		merge(start,end,left,right,mid);
	}
}

int main(void)
{
	int N, *start=NULL, *end=NULL, count=0, last=-1;

	scanf("%d", &N);
	start=(int *)malloc(N*sizeof(int));
	end=(int *)malloc(N*sizeof(int));

	for(int n=0;n<N;n++)
		scanf("%d%d", &start[n], &end[n]);

	mergesort(start,end,0,N-1);

	for(int n=0;n<N;n++)
		if(start[n]>=last)
		{
			count++;
			last=end[n];
		}

	printf("%d\n", count);
	free(start);
	free(end);
	return 0;
}

Solution

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

public class Main {
	static int[] start, end, stemp, etemp;
	
	static void merge(int left,int right) {
		int i=left, mid=(left+right)/2, j=mid+1;
		
		for(int k=left;k<=right;k++)
			if(j>right) {
				stemp[k]=start[i];
				etemp[k]=end[i++];
			}
			else if(i>mid || end[i]>end[j] || end[i]==end[j] && start[i]>start[j]) {
				stemp[k]=start[j];
				etemp[k]=end[j++];
			}
			else {
				stemp[k]=start[i];
				etemp[k]=end[i++];
			}
		
		for(int k=left;k<=right;k++) {
			start[k]=stemp[k];
			end[k]=etemp[k];
		}
	}
	
	static void mergeSort(int left,int right) {
		if(left<right) {
			int mid=(left+right)/2;
			mergeSort(left,mid);
			mergeSort(mid+1,right);
			merge(left,right);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int N=Integer.parseInt(br.readLine()), count=0, last=-1;
		start=new int[N];
		end=new int[N];
		stemp=new int[N];
		etemp=new int[N];
		
		for(int n=0;n<N;n++) {
			st=new StringTokenizer(br.readLine());
			start[n]=Integer.parseInt(st.nextToken());
			end[n]=Integer.parseInt(st.nextToken());
		}
		
		mergeSort(0,N-1);
		
		for(int n=0;n<N;n++)
			if(start[n]>=last) {
				count++;
				last=end[n];
			}

		System.out.println(count);
	}
}