147. 1931(회의실 배정) - 자바

import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ArrayList<int[]> timeList = new ArrayList<>();
		ArrayList<int[]> timeList2 = new ArrayList<>();
		
		// 리스트에 값을 채워줌
		for (int i = 0; i < N; i++) {
			String[] tmp = br.readLine().split(" ");
			int[] tmp2 = { Integer.parseInt(tmp[0]), Integer.parseInt(tmp[1]) };
			timeList.add(tmp2);
			timeList2.add(tmp2);
		}

		// 정렬진행
		Collections.sort(timeList, (e1, e2) -> {
			if (e1[1] == e2[1]) {
				return e1[0] - e2[0];
			} else {
				return e1[1] - e2[1];
			}
		});

		Collections.sort(timeList2, (e1, e2) -> {
			if (e1[1] == e2[1]) {
				return e1[0] - e2[0];
			} else {
				return e1[1] - e2[1];
			}
		});
		
		// 처음 값 선택
		int endMin = timeList.get(0)[1];
		int cnt = 1;
		timeList.remove(0);
		timeList2.remove(0);
		
		// 결과 구하기
		for (int val[] : timeList) {
			if (val[0] < endMin) {
				timeList2.remove(val);
			} else {
				endMin = timeList2.get(0)[1];
				timeList2.remove(val);
				cnt ++;
			}
		}

		System.out.println(cnt);

	}
}

문제요약

회의실 시작시간과 끝시간이 주어진다. 잘 조율해서 가장 많은 회의가 진행될 수 있도록 하자.

설명

'가장 많은' 이라는 조건이 주어졌다. 끝나는 시간 기준으로 오름차순으로 정렬하고 가장 적은 시간부터 생각하자.

입력 예제를 백준 입력으로 진행해 보겠다.

 

먼저 끝나는 시간기준으로 정렬을 한다.

다음과 같이 시간이 정렬될 것 이다.

그러면 맨 처음에 있는 1시 시작 4시 끝을 선택한다.

 

끝나는 시간을 기준으로

이미 1시 시작 4시 끝을 선택했기 때문에 3시시작 5시끝, 0시시작 6시 끝은 선택할 수 없다.

그다음 가장 빠르게 끝나는 회의는 5시 시작 7시 끝이다.

그 다음도 마찬가지이다.

끝나는 시간은 7시 이기 때문에 7시 전에 시작하는 회의들은 선택할 수 없다.

그래서 [3,8] , [5,9] , [6,10]은 지우고 8시 시작 11시 시작 회의가 가장 빠르게 끝나기 때문에 선택한다.

위와 같이 끝을 기준으로 시작 시간이 끝 시간보다 작으면 선택하지 않는 방향으로 문제를 풀어보자.

		// 리스트에 값을 채워줌
		for (int i = 0; i < N; i++) {
			String[] tmp = br.readLine().split(" ");
			int[] tmp2 = { Integer.parseInt(tmp[0]), Integer.parseInt(tmp[1]) };
			timeList.add(tmp2);
			timeList2.add(tmp2);
		}

하나의 리스트는 remove를 통해 인덱스 값을 삭제해줄 것이다.

따라서 원본 하나, 삭제할 리스트 하나 해서 두개의 리스트에 값을 받는다.

 

// 정렬진행
		Collections.sort(timeList, (e1, e2) -> {
			if (e1[1] == e2[1]) {
				return e1[0] - e2[0];
			} else {
				return e1[1] - e2[1];
			}
		});

		Collections.sort(timeList2, (e1, e2) -> {
			if (e1[1] == e2[1]) {
				return e1[0] - e2[0];
			} else {
				return e1[1] - e2[1];
			}
		});

끝나는 시간을 기준으로 값을 정렬한다. 만약 끝나는 시간이 같다면, 시작시간을 기준으로 정렬을한다.

시작 시간도 고려해주는 이유는 만약 시작과 끝 시간이 같을 경우를 대비해야 하기 때문이다.

 

		// 처음 값 선택
		int endMin = timeList.get(0)[1];
		int cnt = 1;
		timeList.remove(0);
		timeList2.remove(0);

맨 처음 값을 설정해준다.

정렬을 했으므로 맨 앞에 있는 회의시간이 가장 빠르게 끝나는 회의이다.

처음 값은 이제 필요 없으므로 삭제해준다. (삭제하지 않으면 나중에 문제가 생긴다.)

		// 결과 구하기
		for (int val[] : timeList) {
			if (val[0] < endMin) {
				timeList2.remove(val);
			} else {
				endMin = timeList2.get(0)[1];
				timeList2.remove(val);
				cnt ++;
			}
		}

timeList에 있는 회의시간을 하나하나 꺼낸다.

위에서 설명한것과 같이 만약 끝나는 시간이 시작시간보다 크면 해당 회의는 진행할 수 없다.

조건에 해당되지 않으면 맨앞에 있는 시간이 다음 회의가 된다 (정렬과 삭제를 통해서 가능한 것)