[1931번] 회의실 배정 ( 탐욕법, 람다식 비교, 메모리 초과)

---

문제들을 풀면서 느낀 점이 있다.
생각한 풀이를 속으로 따라가면서 그에 맞게 구현을 하면 쉽다.
( 무슨 말인지 아는 사람은 알거다! )

---

처음에 구현한 코드는 아래와 같은데 반례가 있다.
처음에 들어올 때 (3,3) (2,3) (1,3) 이 들어온다면
(3,3) (2,3) (1,3) 이 순으로 정렬되므로 앞에 (2,3) (1,3) 얘네를 먼저 실행해 줄 수 없다.
따라서, 정렬할 때 시작이 빠른 순부터 정렬을 해주면 해결된다.

Arrays.sort(arr, Comparator.comparingInt((int[] a) -> a[1]));

위 코드를 아래와 같이 바꿔주면 된다.

Arrays.sort(arr, (o1, o2) -> {
			if (o1[1] == o2[1])
				return o1[0] - o2[0];

			return o1[1] - o2[1];
		});

배열을 정렬할건데, 1번째 인덱스가 서로 같다면 0번째 인덱스가 작은 거를 먼저 정렬해주겠다는 의미이다.

계속 메모리 초과가 났었는데, arr을 [n][n]으로 선언해줘서 그렇다.
arr[n][2]로 선언해줬어야 했는데!
왜 메모리 초과가 나는지 계속 확인했는데, 이걸 실수하다니!ㅜ

입력 값이 2^32 정도니까 nXn 행렬은 2^64가 될거고, 정수니까 2^66 바이트가 될거다.
1mb= 2^20 이므로 128mb= 2^9 * 2^20 = 2^29이므로 초과될 수 밖에 없다.

---

✅ 코드

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

public class Main {
	static int arr[][];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		arr = new int[n][n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			arr[i][0] = start;
			arr[i][1] = end;
		}

		//1번째 인덱스를 기준으로 오름차순
		Arrays.sort(arr, Comparator.comparingInt((int[] a) -> a[1]));

		int cnt = 1;
		int end = 0;

		for (int i = 0; i < arr.length; i++) {
			if (end <= arr[i][0]) {
				cnt++;
				end = arr[i][1];
			}
		}
		System.out.println(cnt);


	}
}