자바(Java) 알고리즘 문제 풀이 - 회의실 배정

문제 이해

- 회의실을 사용할 수 있는 최대 회의수를 찾아라

 

해결 전략

- 회의들을 끝나는 시간을 기준으로 정렬합니다. 

- 하나의 회의를 선택하고, 그 회의의 끝나는 시간 이후에 있는 회의 중

  가장 빠른 회의를 이어서 선택합니다.

- 위의 전략을 반복합니다. 

 

구현

import java.util.*;

class Time implements Comparable<Time>{
    public int s, e;
    Time(int s, int e) {
        this.s = s;
        this.e = e;
    }
    @Override
    public int compareTo(Time o){
        if(this.e==o.e) return this.s-o.s;
		else return this.e-o.e;
    }
}

public class Main {
	public int solution(ArrayList<Time> arr, int n){
		int cnt = 0;
		
		Collections.sort(arr);
		int endTime = 0; 
		endTime = arr.get(0).e;
		cnt += 1;
		
		for(int i=1; i<n; i++){
		    if(arr.get(i).s >= endTime){
		        endTime = arr.get(i).e;
		        cnt += 1;
		    }
		}
		
		return cnt; 
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		ArrayList<Time> arr = new ArrayList<>();
		for(int i=0; i<n; i++){
			int x=kb.nextInt();
			int y=kb.nextInt();
			arr.add(new Time(x, y));
		}
		System.out.println(T.solution(arr, n));
	}
}

 

피드백

- Time 클래스를 구현하고, compareTo 메소드를 오버라이딩 할 수 있어야 합니다.

- compareTo 메소드를 오버라이딩할 때, 끝나는 시간 기준으로 정렬한 후, 

  끝나는 시간이 같으면 시작 시간 기준으로 정렬해야 합니다.