회의실 배정 (greedy)

최준호·2021년 10월 25일
0

알고리즘 강의

목록 보기
75/79

문제

설명

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다.

각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

입력
첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정보가 주어지는데

이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 회의시간은 0시부터 시작한다.

회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)입니다.

코드

public class MeetingRoom {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int input1 = in.nextInt();
        ArrayList<Room> list = new ArrayList<>();
        for(int i=0; i<input1; i++){
            Room room = new Room(in.nextInt(), in.nextInt());
            list.add(room);
        }
        Collections.sort(list);
        int solution = solution(list);
        System.out.println(solution);
    }

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

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

        @Override
        public int compareTo(Room o) {
            if(this.end == o.end) return this.start - o.start;
            else return this.end - o.end;
        }
    }

    static public int solution(ArrayList<Room> list){
        int cnt=0;
        int end = 0;
        for(Room room : list){
            if(end <= room.start){
                end = room.end;
                cnt++;
            }
        }

        return cnt;
    }
}

설명

저번 씨름 선수 선발 문제에서 비교하는 compareTo 부분의 내용만 변경된 문제나 다름 없다. 여기서 중요한 점은 회의가 끝나는 순서대로 오름차순으로 정렬하고 회의 종료시간이 같다면 시작 시간을 비교하여 시작 시간도 오름차순으로 정렬한다는 것이다. 이 부분만 이해한다면 문제는 쉽게 해결할 수 있었다!

profile
코딩을 깔끔하게 하고 싶어하는 초보 개발자 (편하게 글을 쓰기위해 반말체를 사용하고 있습니다! 양해 부탁드려요!) 현재 KakaoVX 근무중입니다!

0개의 댓글