항해99 32일차 TIL(강의실 배정 / 백준)

문제         

레벨:  G5
알고리즘: 그리디
풀이시간: 1시간
힌트 참조 유무: 무

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

1 번째 시도   

• 끝나는 시간으로 정렬 
• 현재 인덱스 끝나는 시간이 다음 인덱스 시작 시간보다 크다면 answer++ 
• 방의 개수를 새는 자료구조 고민 
  •  min변수에 방 최소 개수 담고 우선순위에큐에 끝나는 시간 담기 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[][] times = new int[N][2];
        for (int i = 0; i < N; i++) {
            String[] s = br.readLine().split(" ");
            times[i][0] = Integer.parseInt(s[0]);
            times[i][1] = Integer.parseInt(s[1]);
        }

        Arrays.sort(times, (o1, o2) -> o1[1] == o2[1] ? o1[0] - o2[0] : o1[1] - o2[1]);

        int min = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        //0시간으로 하나 초기화
        pq.add(0);
        for (int i = 0; i < N; i++) {

            //가장 빨리 끝나는 강의실이 현재인덱스 강의 시작 시간보다 빨리 끝나는 경우
            if (pq.peek() <= times[i][0]) {
                pq.poll();
                pq.add(times[i][1]);
            } else {
                pq.add(times[i][1]);
            }

            min = Math.max(min, pq.size());
        }

        System.out.println(min);
    }
}

2 번째 시도  

• 굳이 min변수가 필요 없어 없앴다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[][] times = new int[N][2];
        for (int i = 0; i < N; i++) {
            String[] s = br.readLine().split(" ");
            times[i][0] = Integer.parseInt(s[0]);
            times[i][1] = Integer.parseInt(s[1]);
        }

        Arrays.sort(times, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        //0시간으로 하나 초기화
        pq.add(0);
        for (int i = 0; i < N; i++) {

            //가장 빨리 끝나는 강의실이 현재인덱스 강의 시작 시간보다 빨리 끝나는 경우
            if (pq.peek() <= times[i][0]) {
                pq.poll();
                pq.add(times[i][1]);
            } else {
                pq.add(times[i][1]);
            }
        }

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

 

min 변수만 없앴을 뿐인데 성공했다. 

min 변수가 있어도 현로직이랑 다를 게 없을 것 같은데 왜 틀렸는지 모르겠다.(시간초과도 아니고...)