백준 11000번 : 강의실 배정 (Java)

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

11000번: 강의실 배정

---

[풀이]

• 처음에는 ArrayList를 선언해서 수업의 끝나는 시간을 기준으로 정렬을 하여 add / remove 메소드를 통해 해결하려했습니다.
  • 이렇게 푸니..시간초과가 발생했습니다.
• 우선순위큐를 구현하여 정렬을 이용한 문제였습니다.
• 우선순위큐에는 끝나는 시간을, 배열에는 시작 시간을 기준으로 정렬을 했습니다.
• 첫 수업은 우선순위큐를 기본적으로 넣어줍니다.
• 이후, 반복문에서 만약, 시작시간이 우선순위큐의 끝나는 시간과 비교하여 시작시간이 더 작을 경우, 우선순위큐에서 하나를 뺍니다.
• 또, 현재의 끝나는 시간을 우선순위큐에 넣어줍니다.
• 이러한 과정을 반복할 경우, 우선순위큐의 size()는 필요한 회의실의 개수입니다.
  
  
• 이 문제도 주말에 다시 풀 계획!

---

[코드]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class Schedule {
        int s, t;

        public Schedule(int s, int t) {
            this.s = s;
            this.t = t;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int answer = 0;
        Schedule[] schedules = new Schedule[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            schedules[i] = new Schedule(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        Arrays.sort(schedules, new Comparator<Schedule>() {
            @Override
            public int compare(Schedule o1, Schedule o2) {
                return o1.s == o2.s ? o1.t - o2.t : o1.s - o2.s;
            }
        });
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(schedules[0].t);

        for (int i = 1; i < N; i++) {
            if (priorityQueue.peek() <= schedules[i].s) {
                priorityQueue.poll();
            }
            priorityQueue.add(schedules[i].t);
        }
        answer = priorityQueue.size();
        System.out.println(answer);
    }
}