[BOJ/JAVA] 1374번: 강의실

1374번: 강의실

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다.

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

키워드

• 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

---

구현

• 우선 순위 큐를 이용하여 구현한다.

• static class Lecture
  • number
    • 강의 번호
  • startTime
    • 강의 시작 시각
  • endTime
    • 강의 종료 시각

• lectureClassQueue
  • 강의가 끝나는 시각의 오름차순 정렬

• 강의 데이터를 강의 시작 시각을 기준으로 오름차순 정렬한다.

• 강의 배열을 돌면서 현재 존재하는 강의실에 가장 빨리 끝나는 강의실에 넣을 수 있으면 넣는다.

• 만약 넣을 수 없다면, 강의실을 하나 추가한다.

---

코드

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 java_1374 {
    static int N;
    static List<Lecture> lectureList;

    static class Lecture implements Comparable<Lecture> {
        int number;
        int startTime;
        int endTime;

        public Lecture(int number, int startTime, int endTime) {
            this.number = number;
            this.startTime = startTime;
            this.endTime = endTime;
        }

        @Override
        public int compareTo(Lecture o) {
            return this.startTime - o.startTime;
        }
    }

    static int solution() {
        int result = 0;

        Collections.sort(lectureList);

        // 강의실에 강의를 추가하는 경우

        // 강의실을 추가하는 경우
        // -> 가장 빨리 끝나는 강의 시각 > 추가하려는 강의의 시작 시각

        PriorityQueue<Integer> lectureClassQueue = new PriorityQueue<>();
        lectureClassQueue.add(0);

        for (int i = 0; i < N; i++) {
            Lecture lecture = lectureList.get(i);

            int classEndTime = lectureClassQueue.peek();

            // 강의실에 강의를 추가하는 경우
            if (!(classEndTime > lecture.startTime)) {
                lectureClassQueue.poll();
            }

            lectureClassQueue.add(lecture.endTime);
        }

        result = lectureClassQueue.size();

        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        lectureList = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int number = Integer.parseInt(st.nextToken());
            int startTime = Integer.parseInt(st.nextToken());
            int endTime = Integer.parseInt(st.nextToken());

            lectureList.add(new Lecture(number, startTime, endTime));
        }

        int result = solution();

        System.out.println(result);

        br.close();
    }
}

---

Uploaded by N2T