[그리디] 백준 회의실 배정 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);
}
}
반응형
'개발로그 > 알고리즘' 카테고리의 다른 글
[그리디] 백준 잃어버린 괄호 1541번 (0) | 2023.08.05 |
---|---|
[그리디] 백준 ATM 11399번 (0) | 2023.08.04 |
[그리디] 백준 동전0 11047번 (0) | 2023.08.04 |
그리디 알고리즘 (0) | 2023.08.04 |
프로그래머스 Lv.1 문자열 내 마음대로 정렬하기 (0) | 2023.08.03 |
댓글