[BOJ] 1931번 회의실 배정 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
    static int N, total = 1;
    static ArrayList<Meeting> meetings = new ArrayList<>();

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

        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());
            meetings.add(new Meeting(start, end));
        }

        Collections.sort(meetings);

        Meeting prev = meetings.get(0);
        for (int i = 1; i < meetings.size(); i++) {
            Meeting now = meetings.get(i);
            if (prev.end <= now.start) {
                total++;
                prev = now;
            }
        }
        System.out.println(total);
    }

    static class Meeting implements Comparable<Meeting> {
        int start;
        int end;

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

        @Override
        public int compareTo(Meeting o) {
            if (this.end == o.end) {
                return Integer.compare(this.start, o.start);
            }
            return Integer.compare(this.end, o.end);
        }
    }
}

📄 해설

접근

• 그리디 알고리즘의 기본 문제.
• 회의들을 종료시간이 빠른 순서대로 정렬을 한 뒤, 회의 진행 가능 여부를 판단하면 된다.

과정

• 회의 정보를 입력 받아 회의 리스트를 생성한다.
• 회의 리스트를 종료시간이 빠른 순서대로 정렬하고, 리스트를 순회한다.
• 리스트를 순회하며 이전 회의의 종료 시간보다 시작시간이 같거나 느린 경우에만 회의를 진행 할 수 있다.