알고리즘) 회의실 배정(그리디 알고리즘)

문제 ✨

 한 개의 회의실과 이를 사용하고자 하는 n개의 회의들에 대해 회의실 사용표를 만들려고 한다. 각 회의는 시작시간과 끝나는 시간이 주어지고, 이를 통해 회의실을 사용할 수 있는 최대 수의 회의를 출력한다. (회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다른 회의가 시작될 수 있다. 또한, 회의시간은 0시부터 시작한다.)

풀이 ✨

 먼저 시작하는 것부터 선택하는 것이 아니라 빨리 끝나는 것 부터 선택해야 한다. 만약 끝나는 시간이 일치하는 경우에는 시작하는 시간으로 오름차열 정렬을 해야한다.

작성 코드 ✍️

import java.util.*;

public class Main {
    static int cnt = 0;
    static int n;
    static Item[] list;

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

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

        @Override
        public int compareTo(Item o) {
            return o.end == this.end ? this.start - o.start : this.end - o.end;
        }
    }

    void solution() {
        int last = 0;
        for (int i = 0; i < n; i++) {
            if (last <= list[i].start) {
                last = list[i].end;
                cnt++;
            }
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        list = new Item[n];
        for (int i = 0; i < n; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            list[i] = new Item(start, end);
        }
        Arrays.sort(list);

        main.solution();
        System.out.println(cnt);
    }
}