백준 1931번 : 회의실 배정 자바

 

 

 

🧫 문제 분석

✔️ 출처

회의실 배정 실버 1

 

📖 문제

 

정렬 문제로 

회의가 끝나는 시간을 기준으로 정렬하되 같다면 시작시간을 오름차순으로 정렬해야한다.

주의할 점은 끝나는 시간에 바로 다른 회의가 시작할 수 있다는 것이다. 

 

정렬 후 

마지막 회의 시간 보다 다음 회의의 시작시간이 크거나 같으면 이는 가능한 회의이므로 

마지막 회의시간을 다음 회의가 끝나는 시간으로 바꾼다. 

 

 

종료시간이 같다면 시작시간을 오름차순 정렬을 해야하는 이유

예를 들어보면

4
1  2
2  2
4  4
2  4

 

이것을 끝나는 시간으로만 정렬했을 경우

입력 순서대로 

1 2

2 2

4 4

2 4 

이대로 들어왔을 것이고 

마지막 회의시간은 

2 -> 2-> 4로 되고 

2 4 일때 마지막 회의시간 = 4 이기에 

이 회의는 무시된다. 따라서 잘못된 답을 내놓게 된다. 

 

 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static class Time implements Comparable<Time>{
        int start, end;

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

        @Override
        public int compareTo(Time t) {
            // 끝 시간이 같다면 시작 시간 오름차순, 아니라면 끝시간 오름차순
            return (end == t.end) ? start - t.start : end - t.end;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        PriorityQueue<Time> pq = new PriorityQueue<>();
        int n = Integer.parseInt(br.readLine());
        int lastTime = 0;
        int count = 1;

        // 회의 초기화
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            pq.add(new Time(start, end));
        }

        lastTime = pq.poll().end;

        while (!pq.isEmpty()) {
            Time time = pq.poll();
            if (lastTime <= time.start) {
                lastTime = time.end;
                count++;
            }
        }

        bw.write(count +"");
        bw.flush();
        bw.close();
    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1.  못풀었던 문제인데 다시 찾아서 잘 풀었다.