백준 문제 1931

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

문제 출처: https://www.acmicpc.net

코드

import java.util.Scanner;

public class Main {
	
	public int[][] sort(int[][] inputList) {
		if(inputList.length<2)
			return inputList;
		else {
			return merge(sort(split(inputList).firstList),sort(split(inputList).secondList));
		}
	}
		
	class ListTuple{
		int[][] firstList;
		int[][] secondList;
		
		public ListTuple(int[][] list1, int[][] list2) {
			firstList=list1;
			secondList=list2;
		}
	}
	
	public ListTuple split(int[][] list) {
		int lengthOfInput=list.length;
		int i=0; //counter
		int[][] list1=new int[lengthOfInput/2][2], list2=new int[lengthOfInput-lengthOfInput/2][2];
		for(int[] temp:list) {
			if(i<(int)(lengthOfInput/2))
				list1[i]=temp;
			else
				list2[i-lengthOfInput/2]=temp;
			i++;
		}
		return new ListTuple(list1, list2);
	}
	
	public int[][] merge(int[][] list1, int[][] list2) {
		int length=list1.length+list2.length;
		int[][] result=new int[length][2];
		for(int i=0, j=0;i+j<length;){
			if(i==list1.length) {
				for(;j<list2.length;){
					result[i+j]=list2[j];
					j++;
				}
				break;
			}
			if(j==list2.length) {
				for(;i<list1.length;) {
					result[i+j]=list1[i];
					i++;
				}
				break;
			}
			
			if(list1[i][1]<list2[j][1] || (list1[i][1]==list2[j][1] && list1[i][0]<list2[j][0])) {
				result[i+j]=list1[i];
				i++;
			}
			else {
				result[i+j]=list2[j];
				j++;
			}
		}
		return result;
	}
		
	public int[][] merge(ListTuple tuple) {
		return merge(tuple.firstList,tuple.secondList);
	}
	
	public static void main(String[] args) {
		Main main=new Main();
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();

		int[][] time=new int[N][2];
		int availableTime=0, count=0;
		for(int i=0;i<N;i++) {
			time[i][0]=sc.nextInt();
			time[i][1]=sc.nextInt();
		}
//		for(int i=0;i<N;i++) {
//			time[i][0]=(int)(150*Math.random());
//			time[i][1]=time[i][0]+(int)(150*Math.random());
//			System.out.printf("%d %d,  ",time[i][0],time[i][1]);
//			if(i%10==9)
//				System.out.println();
//		}														
//		long start=System.currentTimeMillis();
		time=main.sort(time);
		for(int i=0;i<N;i++) {
//			System.out.printf("%d %d,  ",time[i][0],time[i][1]);
//			if(i%10==9)
//				System.out.println(); 
			if(availableTime<=time[i][0]) {
				availableTime=time[i][1];
				count++;
			}
		}
		System.out.println(count);

//		System.out.println((System.currentTimeMillis()-start)/1000.0);
	}
}

처음에 문제를 풀 때 끝나는 시간을 기준으로 정렬한 후에, 가능한 회의 중 가장 빨리 끝나는 회의에 회의실을 배정하는 식으로 배치했다.

그렇게 했을 때 답이 다르게 나왔는데, 시작시간을 기준으로 정렬하는 것을 하지 않아서 그랬던 것. 다른 경우는 가능한 회의 수에 영향을 주지 않지만, 시작과 동시에 끝나는 회의가 있는 경우 그 회의는 끝나는 시간이 같은 회의 중 맨 마지막에 위치해 있어야 회의 수를 최대로 할 수 있다.

따라서 시작하자마자 끝나는 회의를 맨 뒤로 밀어도 되고, 아니면 끝나는 시간이 같은 회의들은 시작시간을 기준으로 정렬되도록 해 주면 된다. 나는 시작시간을 기준으로도 정렬되도록 수정.

주석처리한 부분은 실행시간을 확인하기 위한 부분과, 랜덤한 데이터를 집어넣기 위한 부분, 그리고 정렬이 제대로 이루어졌는지 확인하기 위한 부분 등이 있다. 문제를 풀 때 자주 삽입하는 편.