[BaekJoon] 1931 회의실 배정

1.  문제 링크

2.  문제

요약

• 회의 N개에 대한 시작시간과 끝나는 시간이 주어졌을 때, 각 회의가 겹치지 않도록 하면서 한 개의 회의실을 사용할 수 있는 회의의 최대 개수를 구하는 문제입니다.
• 각 회의는 중간에 중단될 수 없고 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있으며 시작시간과 끝나는 시간이 같은 경우는 시작하자마자 끝나는 것입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 회의의 수 N이 주어지고 두 번째 줄부터 N개의 줄에는 2^31 - 1보다 작거나 같은 자연수 또는 0인 각 회의의 시작시간과 끝나는 시간이 주어집니다.
• 출력: 첫 번째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
	public int getMaxTaskNum(Task[] tasks) {
		Arrays.sort(tasks, new Comparator<Task>() {
			public int compare(Task t1, Task t2) {
				if(t1.end == t2.end) {
					return t1.start - t2.start;
				}
				return t1.end - t2.end;
			}
		});
		int prev_end = tasks[0].end;
		int count = 1;
		for(int i = 1; i < tasks.length; i++) {
			if(prev_end <= tasks[i].start) {
				count++;
				prev_end = tasks[i].end;
			}
		}
		return count;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int task_num = Integer.parseInt(br.readLine());
		Task[] tasks = new Task[task_num];
		for(int i = 0; i < task_num; i++) {
			String[] times = br.readLine().split(" ");
			tasks[i] = new Task(Integer.parseInt(times[0]), Integer.parseInt(times[1]));
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMaxTaskNum(tasks) + "\n");
		bw.flush();
		bw.close();
	}
}
class Task {
	int start;
	int end;
	public Task(int start, int end) {
		this.start = start;
		this.end = end;
	}
}

4.  접근

• 이전 회의의 끝나는 시간과 다음 회의의 시작시간이 겹치지 않는 활동에 대해서 끝나는 시간이 빠른 회의들을 선택하면 더 많은 회의를 선택할 수 있기 때문에 이 방법을 이용하여 이 문제를 해결할 수 있습니다.
• 주어진 회의들을 끝나는 시간을 기준으로 오름차순으로 정렬하고 이전 회의와 다음 회의가 겹치지 않도록 하며 끝나는 시간이 빠른 회의들을 순차적으로 선택해나가며 개수를 확인하면 됩니다.

1. 각 회의의 시작시간과 끝나는 시간을 기록할 Task라는 class를 하나 만들고 각 회의들을 저장할 Task 타입의 1차원 배열을 만들어 해당 배열에 주어진 회의들을 설정합니다.
2. 주어진 회의들을 끝나는 시간을 기준으로 오름차순으로 정렬하고 만약 끝나는 시간이 같다면 시작시간이 빠른 순으로 정렬합니다.
3. 정렬된 회의들을 순차적으로 돌며 이전 끝나는 시간보다 해당 회의의 시작 시간이 같거나 더 느린 경우에 회의 개수를 1 증가시킵니다.
4. 모든 회의들을 다 돌았을 때의 회의 개수를 출력합니다.