[백준]그리디 알고리즘/회의실 배정/1931 풀이 JAVA

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다.

각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데

이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.

시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

 

출력

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

 

 

풀이(JAVA)

	import java.io.*;
	import java.util.*;
	public class Main {
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	// 회의 수 N 입력
	int N = Integer.parseInt(br.readLine());
	int[][] schedule = new int[N][2];
	// N개의 회의 시작 시간과 종료 시간 입력
	StringTokenizer st;
	for (int i = 0; i < N; i++) {
	st = new StringTokenizer(br.readLine());
	schedule[i][0] = Integer.parseInt(st.nextToken()); // 시작 시간
	schedule[i][1] = Integer.parseInt(st.nextToken()); // 종료 시간
	}
	// 회의가 일찍 끝나는 순서대로 정렬(빨리 끝나는 회의를 많이 집어 넣는 것이 최댓값)
	Arrays.sort(schedule, new Comparator<int[]>() {
	@Override
	public int compare(int[] o1, int[] o2) {
	// 회의 종료 시간이 같아면 일찍 시작하는 회의부터
	// ex) (시작, 종료) : (1, 2), (3, 3), (2, 3)일 때,
	// (1, 2), (3, 3), (2, 3) 순으로 정렬되면 회의 최대 갯수는 (1, 2), (3, 3)으로 2 이지만
	// 시작 시간이 빠른 순서대로 정렬하면 (1, 2), (2, 3), (3, 3)으로 3개가 됨.
	if (o1[1] == o2[1]) return o1[0] - o2[0];
	return o1[1] - o2[1];
	}
	});
	// 최대 사용 가능한 회의 최대 개수 찾기
	int endTime = 0; // 회의가 끝나는 시간
	int count = 0; // 사용한 회의 갯수
	for (int i = 0; i < N; i++) {
	if (endTime <= schedule[i][0]) { // 회의가 끝나고 바로 시작 가능한 회의가 있으면
	endTime = schedule[i][1]; // 그 회의가 끝나는 시간으로 갱신하고 다시 반복
	count++; // 회의++
	}
	}
	// 출력
	System.out.println(count);
	}
	}

view raw Main.java hosted with ❤ by GitHub