백준 11000 (강의실 배정)

문제

11000번: 강의실 배정

N개의 강의 시작 시간과 끝나는 시간이 주어진다.

강의를 모두 다 수용하는 최소한의 강의실의 개수를 구하는 문제이다.

만약 어떤 강의 시간이 끝나는 시간과 시작하는 시간이 같을 때 해당강의실은 동시에 사용이 가능하다.

---

전형적인 그리디 방법이다.

먼저 강의가 시작하는 시간을 기준으로 오름차순으로 정렬해주었다.

class Class implements Comparable<Class>{
    int start;
    int end;

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

    @Override
    public int compareTo(Class o){ //시작 시간으로 오름차순으로 정렬
        if(this.start == o.start) //만약 시작하는 시간이 같다면 끝나는 시간 기준으로 오름차순 정렬
            return this.end - o.end;
        return this.start - o.start;
    }
}

 

이제 강의들을 순회하면서 어떤 공간에 넣고 새롭게 들어오는 강의의 시작 시간과 어떤 공간에 있는 강의 중에 끝나는 시간이 가장 빠른것과

비교를 해서 똑같은 강의실에서 강의를 할 수 있으면 어떤 공간에 있는 강의를 제거하고 새롭게 들어온 강의를 어떤 공간에 넣어준다.

어떤 공간은 빠르게 새롭게 들어오는 강의 들의 끝나는 시간대로 오름차순으로 정렬을 해줄 수 있는 공간이다.

바로 "우선순위 큐" 이다.

for(Class c : classes){
            if(fastEndtimes.isEmpty()){ //만약 우선순위 큐에 아무것도 없으면 그냥 넣어줌
                fastEndtimes.add(c);
                cnt++;
            }
            else{
                if(fastEndtimes.peek().end <= c.start){  //똑같은 강의실에서 이어서 강의를 할 수 있는 경우
                    fastEndtimes.remove();
                    fastEndtimes.add(c);
                }
                else{ //강의를 이어서 할 수 없는 경우 우선순위 큐에 넣어준다.
                    fastEndtimes.add(c);
                    cnt++;
                }
            }
        }

---

전체 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

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

        int n = Integer.parseInt(st.nextToken());

        List<Class>classes = new ArrayList<>();

        PriorityQueue<Class>fastEndtimes = new PriorityQueue<>(new Comparator<Class>() {
            @Override
            public int compare(Class o1, Class o2) {
                return o1.end - o2.end;
            }
        });




        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            Class c = new Class(start, end);
            classes.add(c);
        }


        Collections.sort(classes);


        int cnt = 0;
        for(Class c : classes){
            if(fastEndtimes.isEmpty()){
                fastEndtimes.add(c);
                cnt++;
            }
            else{
                if(fastEndtimes.peek().end <= c.start){
                    fastEndtimes.remove();
                    fastEndtimes.add(c);
                }
                else{
                    fastEndtimes.add(c);
                    cnt++;
                }
            }
        }

        System.out.println(cnt);
    }
}
class Class implements Comparable<Class>{
    int start;
    int end;

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

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

}