인프런 9-2. 회의실 배정 (자바)

[문제]

한 개의 회의실이 있는데 이를 사용하고자 하는 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, 5), (5, 7)이 회의실을 이용할 수 있다.

---

[문제풀이과정]

이건 그리디 알고리즘 검색하다가 어디선가 본 적 있는듯..
일단 회의를 최대한 많이 해야되기 때문에 일찍 끝나는 애들이 우선이다.
그럼 회의 끝나는 시간을 기준으로 오름차순으로 일단 2차원 배열을 정렬한다.
제일 빨리 끝나는 애들 먼저 넣어놓고 그 다음 애부터 넣을지 말지 결정한다.
그 다음 애는 회의 시작시간이 앞 회의 끝나는 시간보다 앞인지 뒤인지 비교한다.
그 다음애의 회의 시작시간이 앞회의 끝나는 시간보다 뒤여야지 넣어놓는다.
그 다음것도 똑같이 반복한다.

1. 회의의 수 N을 입력받는다.
2. 이차원배열[N][2] 을 만들고 각 회의의 시작시간과 끝 시간을 담는다.
3. 회의가 끝나는 시간인 두번째 숫자[i][1] 기준으로 오름차순으로 정렬한다.
4. 제일 먼저 끝나는 회의를 일단 넣어놓는다. 
그리고 걔의 끝시간을 변수에 담아놓는다. 그리고 회의 수++
5. 그 다음 회의부터 앞 회의 끝나는 시간과 뒷회의 시작시간을 비교한다.
뒷회의 시작시간이 앞회의 끝나는 시간보다 이후여야지 회의 수++되고
끝시간을 이번 회의의 끝시간으로 덮어쓰기 해준다.
6. 마지막에 회의 수를 출력해주면 끝!!

여기까지 12분 걸림

[첫번째로 푼 코드 - 테스트 케이스 오류남]

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
	    int N = sc.nextInt();
	    int[][] meeting = new int[N][2];
	    
	    for(int i = 0 ; i < N ; i++) {
	    	meeting[i][0] = sc.nextInt();
	    	meeting[i][1] = sc.nextInt();
	    }
	    
	    int meetingNum = 0;
	    
	    Arrays.sort(meeting, new Comparator<int[]>() {
	    	// 회의가 먼저 끝나는 순으로 정렬하기!!
	    	
	    	@Override
	    	public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
                // 회의 끝나는 시간 기준 오름차순
	    	}
		});
	    
	    int frontEnd = meeting[0][1];
	    // 앞 회의 끝난 시간에 가장 먼저 끝난 회의 끝시간 넣어놓기
	    meetingNum++;
	    // 제일 먼저 끝나는 회의는 무조건 해야함
	    
	    for(int i = 1 ; i < N ; i++) {
	    	if(meeting[i][0] >= frontEnd) {
	    		frontEnd = meeting[i][1];
	    		// 만약 다음 회의의 시작시간이 앞회의 끝시간보다 뒤면 그 회의의 끝시간을 앞회의 끝시간으로 바꾸고
	    		meetingNum++;
	    		// 회의 하나 더 추가해주기
	    	}
	    }
	    System.out.println(meetingNum);
	  }
}

어랏 그런데 이렇게 하니까 어떤 테스트 케이스에서는 오류 나버림!!

[입력예제 2]

3
3 3
1 3
2 3


[출력예제 2]

2

[예제설명]

(1,3), (3, 3)이 회의실을 이용할 수 있다.

 

문제에서 회의 시작시간과 끝시간이 똑같게 주어질 수 있댔는데 그걸 고려하지 않은것!! 그래서 끝시간 기준 오름차순으로만 정렬하면 조금 부족하다. 끝시간이 같을 경우 시작시간 기준으로 오름차순 정렬을 한 번 더 해줘야 최대한 많은 회의를 담을 수 있다!! 그래서 정렬 조건 하나만 더 추가해주면 된다.

---

[수정해서 패스한 코드]

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
	    int N = sc.nextInt();
	    int[][] meeting = new int[N][2];
	    
	    for(int i = 0 ; i < N ; i++) {
	    	meeting[i][0] = sc.nextInt();
	    	meeting[i][1] = sc.nextInt();
	    }
	    
	    int meetingNum = 0;
	    
	    Arrays.sort(meeting, new Comparator<int[]>() {
	    	// 회의가 먼저 끝나는 순으로 정렬하기!!
	    	
	    	@Override
	    	public int compare(int[] o1, int[] o2) {
	    		if(o1[1] != o2[1]) {
	    			return o1[1] - o2[1];
	    			// 회의 끝나는 시간 기준 오름차순
	    		} else {
	    			return o1[0] - o2[0];
	    			// 회의 끝시간 같으면 시작시간 기준 오름차순
	    		}
	    	}
		});
	    
	    int frontEnd = meeting[0][1];
	    // 앞 회의 끝난 시간에 가장 먼저 끝난 회의 끝시간 넣어놓기
	    meetingNum++;
	    // 제일 먼저 끝나는 회의는 무조건 해야함
	    
	    for(int i = 1 ; i < N ; i++) {
	    	if(meeting[i][0] >= frontEnd) {
	    		frontEnd = meeting[i][1];
	    		// 만약 다음 회의의 시작시간이 앞회의 끝시간보다 뒤면
                	// 그 회의의 끝시간을 앞회의 끝시간으로 바꾸고
	    		meetingNum++;
	    		// 회의 하나 더 추가해주기
	    	}
	    }
	    System.out.println(meetingNum);
	  }
}

 

[후기]

이 문제는 끝시간 기준으로만 오름차순 정렬하면 될 게 아니라 시작시간 기준으로도 오름차순 정렬해야된다는게 포인트인 문제였다!! 그 외에는 9-1 씨름 선수 문제랑 별반 다를게 없다. 암튼 이렇게 가장 최선인 선택을 그때그때 해나가는게 그리디 알고리즘이라는 것!!!