[LeetCode- Ch.2 정렬 & 검색] 5. 미팅룸2 - 최소 회의실 개수 ## (+ PriorityQueue)

https://www.lintcode.com/problem/919/

LintCode 炼码

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

19598번: 최소 회의실 개수

 

이전 문제와 다르게 시작 시간 기준 오름차순 정렬,시작 시간이 같으면 끝나는 시간 기준 오름차순

-> 반례가 존재하기 때문

import java.util.*;

class Main{
    public static void main(String args[]) throws Exception{
        Scanner sc = new Scanner(System.in);
        int N=sc.nextInt();
        int[][] arr =new int[N][2];
        //시작 시간, 끝나는 시간
        for(int i=0;i<N;i++){
            arr[i][0]=sc.nextInt();
            arr[i][1]=sc.nextInt();
        }
        Arrays.sort(arr, (o1, o2) -> {
            if(o1[0] == o2[0]){
                return Integer.compare(o1[1], o2[1]);
            } else {
                return Integer.compare(o1[0], o2[0]);
            }
        });
        int cnt=0;
        int[] end=new int[N];
        Arrays.fill(end, Integer.MIN_VALUE);

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(arr[i][0]>=end[j]){
                    end[j]=arr[i][1];
                    break;
                }
            }
        }
        for(int x:end) {
            if(x!=Integer.MIN_VALUE)
                cnt++;
        }
        System.out.print(cnt);
    }
}

---

끝나는 시간을 담을 배열 생성 후, Integer.MIN_VALUE로 초기화

-> 해당 배열을 돌면서 시작시간과 비교해 해당 값보다 시작시간이 크면, 한 회의실을 사용 -> break;

-> 그렇지 않으면 MIN_VALUE로 남아있으므로, 새로운 회의실이 필요하다는 것을 의미

import java.util.*;

class Main{
    public static void main(String args[]) throws Exception{
        Scanner sc = new Scanner(System.in);
        int N=sc.nextInt();
        int[][] arr =new int[N][2];
        //시작 시간, 끝나는 시간
        for(int i=0;i<N;i++){
            arr[i][0]=sc.nextInt();
            arr[i][1]=sc.nextInt();
        }
        System.out.println(Solution(N, arr));
    }
    private static int Solution(int N, int[][] arr){
        Arrays.sort(arr, (o1, o2) ->o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0]);
        
        int cnt=0;
        int[] end=new int[N];
        Arrays.fill(end, Integer.MIN_VALUE);

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(arr[i][0]>=end[j]){
                    end[j]=arr[i][1];
                    break;
                }
            }
        }
        for(int x:end) {
            if(x!=Integer.MIN_VALUE)
                cnt++;
        }
        return cnt;
    }
}



 

---

시작 시간 오름차순이지만, 시작시간이 같으면 끝나는시간 오름차순

 

public class Solution {

    public int minMeetingRooms(List<Interval> intervals) {
        int n=intervals.size();
        int[] end=new int[n];
        int cnt=0;
        Collections.sort(intervals, (o1, o2) ->o1.start==o2.start?o1.end-o2.end:o1.start-o2.start);
        Arrays.fill(end, Integer.MIN_VALUE);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(end[j]<=intervals.get(i).start){
                    end[j]=intervals.get(i).end;
                    break;
                }
            }
        }
        for(int x:end) if(x!=Integer.MIN_VALUE) cnt++;
        return cnt;
        }
}

---

+) 세련된 코드

1. 리스트를 시작시간 기준 오름차순 정렬

2. 큐에 넣는데, 끝나는 시간 기준 오름차순 정렬되도록 한다.

3. 큐가 비어있으면, 넣고, 비어있지않을 경우 맨 위의 회의실을 꺼내 끝나는 시간과 다음 시작시간을 비교한다

4. 다음 시작 시간이 더 크거나 같을 경우, 해당 회의실을 꺼내고, 다음 회의실을 넣는다.

5. 그렇지 않을 경우, 그대로 회의실을 넣는다.

6. 큐의 크기 == 필요한 회의실 개수

public class Solution {

    public int minMeetingRooms(List<Interval> intervals) {
        Collections.sort(intervals,(a,b)->a.start-b.start);
        Queue<Interval> pq=new PriorityQueue<>((a,b)->a.end-b.end);
        
        for(Interval arr: intervals){
            if(pq.isEmpty()) pq.add(arr);
            else{
                if(pq.peek().end<=arr.start){
                    pq.poll();
                }
                pq.offer(arr);
            }
        }
        return pq.size();
    }
}