Coffee And Coding

- 분류: 그리디 알고리즘

- 문제 링크 : https://www.acmicpc.net/problem/1931

풀이

최대한 많은 회의를 진행할 수 있도록 회의실을 사용하기 위해선 가장 빨리 끝나는 회의순으로 정렬하면 된다. 그러면 가장 많은 수의 회의가 회의실을 이용할 수 있게 된다.

다른 경우들을 살펴보자.

만약 회의가 가장 빨리 시작하는 순으로 정렬할 경우, 아래와 같은 반례가 존재한다. 회의가 가장 빨리 시작하는 순으로 회의실을 이용할 수 있게 할 경우 1개의 회의만이 회의실을 사용할 수 있지만, 최대 사용 가능 수는 3이다.

회의시간이 짧은 순으로 정렬할 경우는 아래와 같은 반례가 존재한다. 짧은 순으로 회의실을 이용할 수 있게 하면 아래의 경우는 1개 회의만이 회의실을 사용할 수 있게 되는데, 최대 2개의 회의가 이용 가능하기 때문이다.

그래서 회의가 가장 빨리 끝나는 순으로 회의실을 이용할 수 있게 해주면, 최대 수를 구할 수 있다.

그런데 여기서도 주의할 점이 있다.

회의를 빨리 끝나는 회의순으로 정렬할 때, 회의가 끝나는 시간이 같을 경우 시작시간이 빠른 순으로 정렬하도록 한다. 아래 그림을 보자. 회의가 끝나는 시간순으로 정렬할 때 시작시간을 고려하지 않으면 3개 회의(빨간색으로 체크한 부분)만이 회의실을 이용할 수 있게 된다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
        int result = 0;
        
        int count = sc.nextInt(); sc.nextLine();
        int meeting[][] = new int[count][2];
        
        for(int i = 0; i<count; i++) {
            meeting[i][0] = sc.nextInt();
            meeting[i][1] = sc.nextInt();
        }
        
        
        // 끝나는 시간 순으로 정렬 (오름차순)
        Arrays.sort(meeting, (o1, o2) -> {
			// 끝나는 시간이 같으면 시작시간이 빠른 순으로 정렬
            if(o1[1] == o2[1]) {
                return Integer.compare(o1[0], o2[0]);
            } else {
                return Integer.compare(o1[1], o2[1]);
            } 
        });
        
        
        int endTime = meeting[0][1]; // 가장 빨리 끝나는 시간
        result++;
        
        for(int i =  1; i<count; i++) {
            if(meeting[i][0] >= endTime ) {
                endTime = meeting[i][1];
                result++;
            } else {
                continue;
            }
        }
        
        System.out.println(result);
	}
}

[java] 2차원 배열 정렬하기

- Arrays.sort()

// 2차원 배열 정렬하기
public static void main(String[] args) {
//
  int[][] arr = {{1, 2}, {2, 3}, {3, 5}, {3, 4}};

  Arrays.sort(arr, (x, y) -> {
  if (x[0] == y[0]) { // 0번째가 같으면
  return x[1] - y[1]; // 1번째를 기준으로 오름차순
  }
  return x[0] - y[0]; // 0번째를 기준으로 오름차순
  });

  for (int i = 0; i < arr.length; i++) {
  System.out.println(arr[i][0] + " , " + arr[i][1]);
}

}