[백준] BOJ 1931 회의실 배정

문제링크 🚩

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

1931번: 회의실 배정

 

​

📕 문제 접근 📕

 

- 시작 시간과 끝 시간을 하나의 리스트로 관리하기 위해 Time이라는 클래스를 정의한다

- 종료 시간을 기준으로 정렬을 한다. 종료 시간이 같다면 시작시간이 짧은걸 우선으로 배치한다.

- 종료 시간이 빨라야 더 많은 회의를 진행 할 수 있기 때문. 

 

 

💻 Code 💻

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class BOJ_1931_회의실배정 {

    public static class Time {
        int start;
        int end;

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

    public static class TimeComparator implements Comparator<Time> {
        @Override
        public int compare(Time t1, Time t2) {
            // 종료 시간이 같으면 시작 시간이 빠른 순으로 정렬
            if (t1.end == t2.end) {
                return Integer.compare(t1.start, t2.start);
            }
            return Integer.compare(t1.end, t2.end);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int TC = Integer.parseInt(br.readLine());

        ArrayList<Time> meetings = new ArrayList<>();

        // 회의 입력 받기
        for (int i = 0; i < TC; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            meetings.add(new Time(start, end));
        }

        // 회의 시간을 끝나는 시간을 기준으로 정렬
        Collections.sort(meetings, new TimeComparator());

        int endTime = 0; // 현재 선택된 회의의 끝나는 시간
        int count = 0;   // 선택한 회의의 수

        // 정렬한 뒤 현재 미팅 시작시간이 마감 시간보다 크면 플러스 -> 정렬을 해뒀기 때문에 그리디한 접근이 가능함

        for (Time meeting : meetings) {
            if (meeting.start >= endTime) {
                endTime = meeting.end;
                count++;
            }
        }

        System.out.println(count);
    }
}

 

 

💻 Code Review💻

 

 

📖 배운점 📖

- 원하는 시간을 기준으로 정렬을 하기 위해 Comparator를 만드는 것이 생각보다 어려웠다.

- 문제 접근이 쉽더라도 구현하기 위해 Java문법을 더욱 연습해야겠다.

    public static class TimeComparator implements Comparator<Time> {
        @Override
        public int compare(Time t1, Time t2) {
            // 종료 시간이 같으면 시작 시간이 빠른 순으로 정렬
            if (t1.end == t2.end) {
                return Integer.compare(t1.start, t2.start);
            }
            return Integer.compare(t1.end, t2.end);
        }
    }