그리디 - 강의실 배정

백준링크 : https://www.acmicpc.net/problem/11000

문제 :

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)
이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

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

문제를 풀기전 항상 생각해야 하는 것들 :

1. 어떤 알고리즘을 사용할 것인가 ?

2. 최대한 구체적으로 구상하기

3. java로 풀 경우 int 값을 벗어나는가 ?

1. 2. 최소의 강의실을 사용해야하기 때문에 시작시간이 가장빠른 것을 기준으로 오름차순 정리를 해준다. 오름차순 정리를 할 때 같은 값일 경우 끝나는 시간이 빠를경우 로 정의해준다.
      이제 첫번째 값의 끝나는 시간을 우선순위큐에 넣어준다. 그리고 다음 시작시간이랑 비교하여 넣어주는데 이때 만약 우선순위큐에서 꺼낸 값이 시작시간보다 작거나 같을경우 큐를 꺼낸 후 종료시간을 넣어준다.아닐경우 큐를 꺼내지 않고 종료시간을 넣어준다. 전부 반복 후 큐의 개수를 구하면 된다.

2. int 사용가능

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

class Lecture implements Comparable<Lecture>{
	private int si;
	private int ti;
	public void setSi(int si){
		this.si = si;
	}
	public int getSi(){
		return this.si;
	}
	public void setTi(int ti){
		this.ti = ti;
	}
	public int getTi(){
		return this.ti;
	}	
	public Lecture(int si, int ti){
		this.si = si;
		this.ti = ti;
	}
	@Override
	public int compareTo(Lecture other){
		if(this.si == other.si){
			return this.ti >= other.ti ? 1: -1;
		}
		return this.si >= other.si ? 1: -1;
	}
}

public class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		ArrayList<Lecture>lectures = new ArrayList<>();
		for(int i = 0 ; i < n  ;i++){
			st = new StringTokenizer(br.readLine());
			int si = Integer.parseInt(st.nextToken());
			int ti = Integer.parseInt(st.nextToken());
			lectures.add(new Lecture(si, ti));
		}
		Collections.sort(lectures);
		PriorityQueue<Integer>pq = new PriorityQueue<>();
		for(Lecture lec : lectures){
			int ti = lec.getTi();
			if(!pq.isEmpty() && pq.peek() <= lec.getSi()){
				pq.poll();
			}
			pq.add(ti);
		}
		System.out.println(pq.size());
	}
}