[백준] 11000 강의실 배정

문제 출처: https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

1. 입력

: 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

: 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)

 

2. 출력

: 강의실의 개수를 출력하라.

 

3. 풀이

: 먼저 입력받은 수업의 시작시간과 종료시간을 저장할 수 있는 자료구조 Lesson을 만든다.

: Lesson을 저장할 수 있는 list를 만드는데 정렬시키기 위해 comparable을 구현한다.

: 정렬은 강의의 시작시간이 빠른 순으로 정렬하고 만약 시작시간이 같다면 종료시간이 빠른 순으로 정렬한다.

: 리스트를 순회하며 pq에 끝나는 시간을 저장할 수 있도록 한다.

: pq에는 Integer 값이 들어가 가장 작은 수부터 뱉어내기 때문에 지금까지 각 강의실에서 진행된 수업 중 가장 종료시간이 빠른 수업의 종료시간을 뽑아낼 수 있게 된다.

: 이렇게 해서 마지막에 pq에 남은 수업의 수가 답이 된다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 강의실배정 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static class Lesson implements Comparable<Lesson>{
		int start, end;

		public Lesson(int start, int end) {
			super();
			this.start = start;
			this.end = end;
		}

		@Override
		public int compareTo(Lesson o) {
			if(this.start != o.start) return this.start-o.start;
			return o.end - this.end ;
		}
		
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		List<Lesson> list = new ArrayList<>();
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			list.add(new Lesson(start, end));
		}
		Collections.sort(list);
		for(int i = 0; i < N; i++) {
			Lesson cur = list.get(i);
			if(!pq.isEmpty() && pq.peek() <= cur.start) {
				pq.poll();
			}
			pq.offer(cur.end);
		}
		System.out.println(pq.size());
	}
}