[BOJ-1931][Greedy] 회의실배정 - Java

문제 바로가기

1931번: 회의실배정

 

회의실을 사용할 수 있는 회의의 최대 개수를 구하면 됩니다.

Greedy Algorithm의 대표적인 문제입니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Meeting implements Comparable<Meeting>{
    int start, end;

    public Meeting(int start, int end) {
        super();
        this.start = start;
        this.end = end;
    }
    @Override
    public int compareTo(Meeting o) {
        if(this.end == o.end) return this.start - o.start;
        return this.end - o.end;
    }
}

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(in.readLine());
        Meeting[] m = new Meeting[N];
        int ans = 1;

        for(int i = 0; i< N; i++) {
            st = new StringTokenizer(in.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            m[i] = new Meeting(s, e);
        }
        Arrays.sort(m);

        int endPoint = m[0].end;
        for(int i = 1; i< N; i++) {
            if(endPoint <= m[i].start){
                ans++;
                endPoint = m[i].end;
            }
        }
        System.out.println(ans);
    }
}

 

입력 데이터들을 끝나는 시간을 기준으로 정렬해줍니다. 이 때 끝나는 시간이 같으면 시작 시간을 오름차순으로 정렬해줍니다.

 

 

내 입맛대로 정렬하고 싶을 때, Comparable 인터페이스를 객체 자신이 상속받아 compareTo 메소드를 구현해도 되고, Comparator 인터페이스를 상속받은 새로운 Comparator 클래스를 만들어 그 안에 compare 메소드를 구현해도 됩니다.

 

 

Comparator를 활용하면 이렇슴니다.

class myComparator implements Comparator<Meeting>{
    @Override
    public int compare(Meeting o1, Meeting o2) {
        if(o1.end == o2.end) return o1.start - o2.start;
        return o1.end - o2.end;
    }
}


...


//in main()
    Arrays.sort(m, new myComparator());

조만간 자바 관련 친구들을 정리해서 올려야겠슴다..

 

 

 

감사함니다 ㅎ.ㅎ