[백준] 11000 : 강의실 배정 - Python

문제

강의의 시작시간, 끝시간 주어짐
모든 수업이 가능한 최소의 강의실 개수 구하기

내 코드

import heapq
import sys
sys.stdin = open("input.txt", "rt")

# 각 수업 시작시간, 끝시간 존재
# 기준 2개
# n <= 200,000
n = int(input())
data = []
for _ in range(n):
    start,end = map(int, input().split())
    data.append((start,end))

data.sort(key = lambda x : (x[0], x[1])) # 시작시간으로 먼저 오름차순 정렬하는 것이 핵심 !

heap = [] # 힙에는 끝나는 시간만 저장.
cnt = 0

for start,end in data:
    if heap and heap[0] <= start: # 현재 강의실이 가장 빨리 끝나는 강의의 끝나는 시간보다 같거나 크면 이어서 가능
        heapq.heappop(heap) # 현재꺼 없애고 이어가면 돼
    heapq.heappush(heap, end) # 현재꺼는 계속 넣어야 해

res = len(heap)
print(res)

코멘트

활동 선택문제의 기본
링크텍스트[백준 회의실 배정] 문제랑 같다고 생각해서 잘못 접근.

나는 끝나는 시간 기준으로 오름차순 정렬을 시도한 후 힙에 가장 빨리 끝나는 강의의 끝나는 시간을 넣었다.

애초에 접근부터 잘못했음.
-> 강의를 가장 빨리 시작하는 순으로 정렬했어야 했다. 그래야 힙을 강의 끝나는 시간을 갱신할 때 다른 비교없이 heappop만으로 끝낼 수 있음

-> 가장 빨리 시작하는 순으로 정렬한다면 뒤에 들어오는 값 때문에 for문을 돌려줄 필요가 없다.
즉, heappop하고 뒤에 들어오는 강의의 시작시간이 더 짧으면 어떡하지?라는 고민을 할 필요가 사라짐.

현재 강의의 종료시간과 다음 열릴 강의의 시작시간 관계에 집중했어야 했음
1. 현재 강의가 끝나는 시간보다 다음 강의의 시작시간이 빠르면 강의실 하나 더 필요
2. 현재 강의가 끝나는 시간보다 다음 회의 시작시작이 느리면 현재 이어서 가능

이 문제는 끝나는 시간이 아니라 시작시간으로 정렬하는 것이 주요했음...

우선순위큐가 비어있지 않고, 현재 강의의 시작시간이 우선순위 큐의 최소 종료시간보다 크거나 같으면, 해당 강의실을 사용할 수 있으므로 우선순위 큐에서 종료시간 제거.
현재 강의의 종료시간을 우선순위 큐에 계속 추가.
최종적으로 우선순위 큐의 크기가 필요한 최소 강의실의 개수.

시작시간을 기준으로 오름차순 정렬, 우선순위 큐를 사용하여 강의실 효율적으로 배정하는 것이 핵심.

직접 짜면서 내 코드가 예제 테케가 돌아가는지 확인하면서 진행하자.

java 코드

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



public class Main {

    static int n;
    private static class Data implements Comparable<Data>{
        int start, end;

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

        @Override
        public int compareTo(Data data) {
            if (this.start == data.start) {
                return this.end - data.end;
            }
            return this.start - data.start;
        }
    }

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

        n = Integer.parseInt(br.readLine());
        List<Data> data = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            data.add(new Data(start, end));
        }
        Collections.sort(data); // ! 시작시간 오름차순, 그 후 끝나는 시간 오름차순
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> a.compareTo(b)); // ! 오름차순 정렬 -> 끝나는 시간만

        for (Data d : data) {
            int start = d.start;
            int end = d.end;
            if (!pq.isEmpty() && pq.peek() <= start) { // ! 큐 안 비어있으면서, 현재 강의의 시작시간이 우선순위 큐에 들어있는 가장 빨리 끝나는 시간보다 같거나 크면 이어서 가능
                pq.poll(); // ! 마지막 꺼 버려
            }
            pq.offer(end); // ! 마지막 시간은 언제나 갱신.
        }

        int res = pq.size();
        System.out.println(res);
    }
}