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

0. 출처

백준 11000번 문제입니다.

 

1. 문제

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

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

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

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

(1) 입력

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

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

(2) 출력

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

 

2. 문제 풀이

(1) 문제 풀이 방법

이 문제는 그리디 알고리즘을 활용해 풀 수 있는데요. 어떻게 그리디 알고리즘이 적용되는건지 예시를 통해 알아봅시다!

 

예시에서는 (1,3) (2,4) (3,5) 강의 3개가 주어집니다.

(1,3) 강의와 (2,4) 강의는 겹치는 부분이 있습니다. 같은 강의실에서 강의를 할 수 없으므로 2개의 강의실이 존재하는 상황입니다.

그 다음으로 (3,5) 강의는 

 

• 새로운 강의실에서 강의를 한다.
• (1,3) 강의를 했던 강의실에서 강의를 한다.

두 가지 선택지가 있습니다. 그러나 최소의 강의실을 사용해야하는 문제인 만큼 당연히 (1,3) 강의를 했던 강의실을 선택해야하죠!

 

그럼 여기에는 어떤 규칙이 있을까요? 앞선 강의들의 종료 시간 중 가장 빠른 것과 그 다음 강의의 시작 시간을 비교해서 강의실을 새로 사용할지 기존의 강의실을 이어서 사용할지 결정하면 됩니다!

 

이를 위해서는 정렬이 필요하겠죠?!

우선 입력받는 강의들을 시작 시간을 기준으로 오름차순 정렬을 하고, 만약 시작 시간이 같은 강의가 있다면 종료 시간이 더 빠른 강의가 앞에 위치하도록 해줍니다. 저는 우선순위큐를 활용해서 정렬을 했습니다.

static class Lecture implements Comparable<Lecture>{
    int start; // 시작 시간
    int end; // 종료 시간

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

    @Override
    public int compareTo(Lecture l) {
        if(this.start == l.start) { // 시작 시간이 같다면 종료 시간이 더 빠른 것으로
            return Integer.compare(this.end, l.end);
        }

        return Integer.compare(this.start, l.start); // 기본적으로 시작 시간을 기준으로 정렬
    }
}

그 이후에는 큐가 빌 때까지 가장 작은 종료 시간을 체크하며 강의를 배치하면 됩니다!

(2) 코드 (Java)

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

public class Main {
    
    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;

        PriorityQueue<Lecture> q = new PriorityQueue<>();
        PriorityQueue<Integer> endTime = new PriorityQueue<>();
        StringTokenizer st;
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            q.add(new Lecture(start, end));
        }

        while(!q.isEmpty()) {
            Lecture now = q.poll();

            if(endTime.size() == 0 || now.start<endTime.peek()) {
                endTime.add(now.end);
                answer++;
            } else {
                endTime.poll();
                endTime.add(now.end);
            }
        }

        
		System.out.println(answer);
		br.close();
    }
    
    
    static class Lecture implements Comparable<Lecture>{
        int start;
        int end;

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

        @Override
        public int compareTo(Lecture l) {
            if(this.start == l.start) {
                return Integer.compare(this.end, l.end);
            }

            return Integer.compare(this.start, l.start);
        }
    }
}

 

(3) 결과