[알고리즘] 백준 1931 : 회의실 배정 - JAVA

문제

1931번: 회의실 배정

문제이해

한 개의 회의실을 두고 N개의 회의에 대한 회의 시작 시간과 종료시간이 주어진다 이 때 회의실을 사용할 수 있는 회의의 최대 개수를 구하는 문제

1. 회의는 끝나는 것과 동시에 다음 회의가 시작될 수 있다

2. 회의의 시작시간과 종료시간이 같으면 시작하자마자 끝나는 것 ex) 1 3, 3 3, 3 4이면 답은 3

 

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다

• N
• 시작시간  종료시간

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다

---

풀이

 

처음은 짧은 회의들을 먼저 선택하면 될 줄 알았으나 입력이 1 4, 3 5, 4 7 이라 했을 때, 아래와 그림을 보듯 답은 1 4, 4 7을 선택해 2개가 나와야하지만 3 5하나만을 선택해 1개가 나오게 되어 다른 방법이 필요하다 생각했습니다

 

다음 방법으로는 종료시간이 빠른 순서대로 정렬하였습니다 이 때 문제는 입력이 1 4, 7 7, 4 7 이라 했을 때, 답은 1 4, 4 7,  7 7 로 3개가 나와야 하지만 정렬순서에 따라 1 4와 7 7로 2개가 나오게 됩니다. 

그렇기 때문에 종료시간이 같다면 시작시간을 기준으로 정렬해 주어야 한다는 걸 주의 해야 합니다.

---

코드

import java.util.*;

public class Main {
    public static void main(String[] args){
        Main main = new Main();
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        List<Conference> con_list = new ArrayList<>();

        for(int i = 0; i < N; i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            con_list.add(new Conference(start, end));
        }
		//	종료시간을 기준으로 정렬
        Collections.sort(con_list);

        int cur_end = -1;
        int answer = 0;
        //	회의 카운트
        for(Conference c : con_list){
            if(cur_end <= c.start){
                cur_end = c.end;
                answer++;
            }
        }
        System.out.println(answer);
    }

    static class Conference implements Comparable<Conference>{
        int start;
        int end;
        public Conference(int start, int end){
            this.start = start;
            this.end = end;
        }
        //  종료시간이 같다면 시작시간을 기준으로 정렬
        @Override
        public int compareTo(Conference conference){
            if(conference.end < end){
                return 1;
            }
            else if(conference.end > end){
                return -1;
            }
            else if(conference.start < start){
                return 1;
            }
            else if(conference.start > start){
                return -1;
            }
            return 0;
        }
    }
}