회의실 배정

회의실 배정

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

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

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

입력 설명

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

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

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

출력 설명

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

입력 1

5
1 4
2 3
3 5
4 6
5 7

출력 1

3

입력 2

3
3 3
1 3
2 3

출력 2

2

틀린 구현 코드

 public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Conference[] list = new Conference[n];
        for(int i=0;i<n;i++){
            list[i] = new Conference(in.nextInt(),in.nextInt());
        }


        int answer = Integer.MIN_VALUE;
        Conference c1,c2;
        for(int i=0;i<n;i++) {
            int count = 0;
            c1 = list[i];
            for (int j = 0; j < n; j++) {
                if(i!=j) {
                    c2 = list[j];
                    if(c1.end<=c2.start){
                        count++;
                    }
                }
            }
            if(answer<=count){
                answer = count;
            }
        }

        System.out.println(answer);
    }

    static class Conference {
        int start;
        int end;

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

원래 생각은 이중 for문을 돌면서 비교하는 식으로 짰음. 테스트케이스는 맞는데 제출하니 오류로 뜸. 백준에서는 시간초과.
시간초과는 이중 for문으로 인해 생긴 듯 했음.

모범답안 참고 후 구현 코드

 public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Conference[] list = new Conference[n];
        for(int i=0;i<n;i++){
            list[i] = new Conference(in.nextInt(),in.nextInt());
        }

        Arrays.sort(list);

        int et = 0,count =0;
        for(Conference c : list){
            if(c.start>=et){
                count++;
                et = c.end;
            }
        }

        System.out.println(count);

    }

    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 o) {
            if(this.end == o.end) return this.start-o.start;
            return this.end-o.end;
        }
    }

end 기준 정렬 이유:
start기준으로 작은 애들부터 센다면

|---------------------|
|----| |-----------|

이런 경우에는 2개가 아닌 1개로 카운트되어버림.
이를 방지하기 위해 end기준으로 정렬. 만약 end가 같다면 start기준으로 오름차순 정렬.

정렬 후 start>=end로 비교하는 아이디어는 같음.