[백준 1931] 회의실 배정 (JAVA)

백준 1931번 문제  - 회의실 배정

1931번: 회의실 배정

---

문제 분석

 

• 회의 시작, 끝 시간이 주어지고, 이를 토대로 회의실 사용표를 정한다.
• 이때 한 회의실에 몇개의 회의가 주어지는지를 구하고, 최대 회의 수를 출력해라.

 

---

 

해결 키 포인트

 

 

• 그리디 알고리즘
• 회의 시간에 따라 오름차순 정렬
  • 회의 끝 시간으로 정렬
  • 회의 끝 시간이 같을 경우, 시간 시간으로 정렬

 

---

그리디 알고리즘 (탐욕 알고리즘)

 

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.

 

쉽게 말해, 지금의 최선 = 전체의 최선

 

뒤에 사진에서 서울에서 부산까지의 최소거리를 구하고자할 때, 
서울에서 대구의 최솟 값을 선택하고, 대구에서 부산까지의 최솟값을 선택하는 알고리즘

파이썬 알고리즘 인터뷰 (나무위키)

 

---

코드

import java.io.*;
import java.util.*;

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

        // N 입력
        int N = Integer.parseInt(br.readLine());

        // 수 입력
        ArrayList<Meeting> meetings = new ArrayList<>();

        // 회의 입력
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int startClock = Integer.parseInt(st.nextToken());
            int endClock = Integer.parseInt(st.nextToken());

            meetings.add(new Meeting(startClock, endClock));
        }

        // 정렬
        Collections.sort(meetings, new MeetingComparator());

        int count = 0;

        // 현재 확인할 회의가 더이상 없을 때까지
        int i = 0;
        while(i < N) {
            // 얻어내고 count 증가
            Meeting m = meetings.get(i++);
            count++;

            // 현재 확인할 회의가 더이상 없을 때까지
            while (i<N){
                // 방금 index 회의의 start 시간이 앞서 뽑아낸 회의의 end 시간보다 같거나 클 때까지
                Meeting newM = meetings.get(i);
                if(m.end <= newM.start) {
                    break;
                }
                i++;
            }
        }

        System.out.println(count);
    }

    public static class MeetingComparator implements Comparator<Meeting> {
        @Override
        public int compare(Meeting o1, Meeting o2) {
            // end가 동일할 경우, start가 작은 순으로
            if(o1.end == o2.end) {
                return o1.start - o2.start;
            }
            // end가 작은 순으로
            return o1.end - o2.end;
        }
    }

    public static class Meeting {
        public int start;
        public int end;

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