[그리디]백준 회의실 배정 1931번

[그리디] 백준 회의실 배정 1931번

---

문제 설명

한 개의 회의실에서 N개의 회의를 한다.

각 회의 I에 대해서는 시작~종료시간이 주어진다.

각 회의가 겹치지 않게 하면서

회의실을 사용할 수 있는 회의의 최대값을 구하라.

단, 회의는 중간에 중단될 수 없고

시작시간과 끝나는 시간이 같을 수도 있다. 

 

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데

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

시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

---

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

** 풀이 방법

 

회의의 개수 N을 입력받는다.

[N][2]크기의 배열을 생성해서

시작시간과 종료시간을 입력받는다.

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int A[][] = new int[N][2];
for (int i=0; i<N; i++) {
    A[i][0] = sc.nextInt();
    A[i][1] = sc.nextInt();
}

 

A배열을 compare메서드를

오버라이딩해서 오름차순으로 정렬한다.

종료시간이 같을 때,

시작 시간이 빠른 순서로 정렬!!

 Arrays.sort(A, new Comparator<int[]>() {
    @Override
    public int compare(int[] S, int[] E) {
        if (S[1] == E[1]) {
            return S[0]-E[0];
        }
        return S[1] - E[1];
    }
});

 

A배열에 인덱스 순서대로 접근해서

앞 회의의 종료 시간보다

시작 시간이 빠른 회의가 나온 경우

현재 회의의 종료 시간으로 end를 업데이트하고

count를 1 증가시킨다.

for문이 끝나고 count를 출력한다.

int end = -1;
int count = 0;
for (int i=0; i<N; i++) {
    if (A[i][0] >= end) {
        end = A[i][1];
        count++;
    }
}
System.out.println(count);

 

<> 전체 코드 </>

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int A[][] = new int[N][2];
        for (int i=0; i<N; i++) {
            A[i][0] = sc.nextInt();
            A[i][1] = sc.nextInt();
        }
        
        Arrays.sort(A, new Comparator<int[]>() {
            @Override
            public int compare(int[] S, int[] E) {
                if (S[1] == E[1]) {
                    return S[0]-E[0];
                }
                return S[1] - E[1];
            }
        });
        
        int end = -1;
        int count = 0;
        for (int i=0; i<N; i++) {
            if (A[i][0] >= end) {
                end = A[i][1];
                count++;
            }
        }
        System.out.println(count);
    }
}