회의실 배정

문제

---

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

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

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

 

입력

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

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

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

출력 

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

 

예시

5
1 4
2 3
3 5
4 6
5 7

 

Key Point

---

• ㅇㅇㅇ

 

종료 시간 기준 오름차순 정렬

 

 

풀이

---

내 풀이

collection 안쓰고 해보려 했는데 실패

class Meeting{
    public int s,e;
    public Meeting(int s, int e){
        this.s = s;
        this.e = e;
    }
    public void compare(Meeting o){
        int cnt =0;
        if(this.e <=o.s){
            cnt++;
        }
        System.out.println(cnt);
    }
}
public class Main {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int s,e;
        ArrayList<Meeting> arr = new ArrayList<>();
        for(int i =0; i<n; i++){
            s= in.nextInt();
            e = in.nextInt();
            arr.add(new Meeting(s,e));
        }
        //Meeting.compare 호출 어케해
    }
}

 

정답 풀이(Comparable implements)

class Meeting implements Comparable<Meeting>{
    int s,e;
    public  Meeting(int s,int e){
        this.s=s;
        this.e=e;
    }
    @Override
    public int compareTo(Meeting o) {
        //종료 시간이 같을 경우 시작 시간 오름차순 정렬
        if (this.e==o.e){
            return this.s-o.s;
        }
        //그 외 종료시간 오름차순 정렬
        else return this.e-o.e;
    }
}
public class Main {
    public int solution(ArrayList<Meeting> arr){
        int cnt=0;
        Collections.sort(arr);
        for(Meeting x : arr){
            System.out.print(x.s + " ");
            System.out.println();
        }
        int temp = 0;
        for(Meeting x : arr){
            //이전 회의의 종료시간보다 다음 회의 시작 시간이 크거나 같으면 cnt++, temp에 다음 회의 종료시간 저장
            if(x.s>=temp){
                cnt++;
                temp = x.e;
            }
        }
        return cnt;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int s,e;
        ArrayList<Meeting> arr = new ArrayList<>();
        for(int i =0; i<n; i++){
            s= in.nextInt();
            e = in.nextInt();
            arr.add(new Meeting(s,e));
        }
        System.out.println(T.solution(arr));
    }
}

 

다른 풀이(Comparator)

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

        int arr[][] = new int[n][2];
        for(int i =0; i<n; i++){
            arr[i][0]=in.nextInt(); //시작 시간
            arr[i][1]=in.nextInt(); //종료 시간
        }
        Arrays.sort(arr, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1] == o2[1]){
                    return o1[0] -o2[0];
                }
                return  o1[1] -o2[1];
            }
        });
        int cnt =0;
        int et=0;
        for(int i = 0; i < n; i++) {
            // 직전 종료시간이 다음 회의 시작 시간보다 작거나 같다면 갱신
            if(et <= arr[i][0]) {
                et = arr[i][1];
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}