[골드 5] 강의실 배정

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

옛날 회의실 배정 기억나서 그렇게 풀었다가 틀림

문제가 이해가 그냥 ㅈㄴ 안 됨 무슨 말인지 모르겠음

 

아 그니까 모든 시간을 검사해서 겹치는 max가 몇 개인지 구하는 문제구나

근데 모든 시간을 검사하면 당연히 시간초과 나겠지?

 

일단 보니까 시작 시간으로 정렬 왜? 시작한 시간부터 이제 강의실 하나를 차지하는 거야

그럼 다음 시간을 맞이했을 때 쓰던 강의실들 끝났으면 빼줘야지?

그래서 pQ로 풀어야 한다~

 

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int N;
		int[][] arr;

		N = Integer.parseInt(br.readLine());
		arr = new int[N][2];

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

		////////////////////////////////////////////////////

		Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if (o2[0] > o1[0])
					return -1;
				else if (o2[0] == o1[0])
					return 0;
				else
					return 1;
			}
		});

		int answer = 0;
		PriorityQueue<Integer> pQ = new PriorityQueue<>();
		for (int i = 0; i < N; i++) {
			if (pQ.isEmpty()) {
				pQ.add(arr[i][1]);
			} else {
				while (!pQ.isEmpty()) {
					if (pQ.peek() <= arr[i][0])
						pQ.remove();
					else
						break;
				}
				pQ.add(arr[i][1]);
			}

			answer = Math.max(pQ.size(), answer);
		}

		System.out.println(answer);

	}
}