14. 강의실 배정 (백준)

가. 문제파악

 1. 유형 : 그리디

    -   되게 자주보이는 유형인데 생각보다 접근하기가 쉽지 않는 것 같다.

    -   핵심은 이전 스케줄에 대한 추가,삭제를 어떻게 처리할 것 인가! 이다.

 

나. 코드 

 1. 풀이 :  정렬과 타입

    -   스케쥴을 시점별로 따로따로 분리해서 풀었다. 즉 start 와 end를 따로 하나의 요소로서 정렬하여 푼다.

    -   주의할점은 수업은 동시에 진행되는 조건이 있기 때문에 시간이 같으면 end 먼저 처리해야한다. 

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        Scanner sc = new Scanner(System.in);
        List<Time>  list = new ArrayList<>();
        int n = sc.nextInt();

        for(int i = 0; i < n; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            list.add(new Time(s,"s"));
            list.add(new Time(e,"e"));
        }

        int cnt = 0;
        int res = 0;
        
        Collections.sort(list);

        for(Time t : list){
            if("e".equals(t.type)){
                cnt--;
            }else {
                cnt++;
            }
            res = Math.max(res, cnt); 
        }
        System.out.println(res);
    }

    static class Time implements Comparable<Time>{
        int time;
        String type;

        public Time(int time, String type) {
            this.time = time;
            this.type = type;
        }

        @Override
        public int compareTo(Time o) {
            if(this.time == o.time){
                return this.type.compareTo(o.type);
            }
            return Integer.compare(this.time,o.time);
        }
    }
}

 

 2. 풀이 :  우선순위큐

    -  다른사람들의 풀이를 보았는데 우선순위큐를 이용해서 그전에 스케쥴을 담아서 처리하고 있었다.

          =>  우선순위큐로 강의가 끝나는 시간이 계속 담아져 있는 형태!

    -  클래스를 쓰지않아서 좀 더 깔끔한것 같다. 이게 속도나 메모리나 더 좋았지만 생각보다 크게 차이나지 않았다.

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][2];
        for(int i = 0; i < n; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            arr[i][0] = s;
            arr[i][1] = e;
        }

        Arrays.sort(arr, (o1, o2) -> {
            if(o1[0] == o2[0]){
                return Integer.compare(o1[1],o2[1]);
            }
            return Integer.compare(o1[0],o2[0]);
        });

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(arr[0][1]);

        for(int i = 1; i < n; i++) {
           int prevEnd = pq.peek();
           int curStart = arr[i][0];
            if(curStart >= prevEnd){
                pq.poll();
            }
            pq.add(arr[i][1]);
        }

        System.out.println(pq.size());
    }
}

 

 

 

출처