[BOJ] 11000번 강의실 배정(java)
문제
풀이
우선순위 큐(PriorityQueue) 활용
우선순위 큐란? 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조
문제에서는 강의가 가장 일찍 끝나는 강의실이 우선순위로 배정되어야 함(PriorityQueue Default)
강의의 start와 end를 int[]로 입력받아 저장.끝나는 시간을 기준으로 오름차 순 정렬.첫 번째 원소의 endTime을 큐에 먼저 넣고, 반복문 수행현재 가장 일찍 끝나는 강의 시간(time.peek())이 비교하는 강의의 시작 시간(lectures[i][0]) 보다 크다면 강의 진행 가능.이 경우, 해당 강의실의 endTime을 재 설정 해주어야 하므로 poll한 후 다시 offer 수행최종적으로 결과값인 큐의 사이즈를 출력
코드
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));
int N = Integer.parseInt(br.readLine());
int[][] lectures = new int[N][2];
for(int i =0 ; i< N ; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
lectures[i][0] = Integer.parseInt(st.nextToken());
lectures[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(lectures, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0] == o2[0]) return o1[1] - o2[1];
return o1[0] - o2[0];
}
});
PriorityQueue<Integer> time = new PriorityQueue<>();
time.offer(lectures[0][1]);
for(int i = 1; i<lectures.length ; i++) {
if(time.peek() <= lectures[i][0]) time.poll();
time.offer(lectures[i][1]);
}
System.out.println(time.size());
}
}
Author And Source
이 문제에 관하여([BOJ] 11000번 강의실 배정(java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dot2__/BOJ-11000번-강의실-배정java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)