N개의 회의가 주어지고, 각 회의마다 시작시간과 끝나는 시간이 주어진다. 각 회의가 겹치지 않게 하면서 최대한 많이 회의를 사용할 수 있는 개수를 구하라.
<조건> 회의의 시작시간과 끝나는 시간이 같을 수 있다.
<풀이> 그리디 알고리즘으로 접근하자. class를 선언해서 시작시간과 끝나는 시간을 저장하자. 이 클래스 배열을 끝나는 시간 기준으로 오름차순 정렬을 하자. 루프를 돌리면서 지금 회의의 끝나는 시간과 다음 회의의 시작 시간을 비교하자. 다음 회의의 시작 시간이 같거나 더 크면 회의 갯수를 누적합 시킨다. 선택한 회의의 종료시간으로 업데이트 하고 다음 회의의 시작시간과 비교 한다.
import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.lang.Comparable;
//[백준] 1931번 - 회의실 배정 (Java)
public class Main {
static int N;
//static Meeting A[];
static ArrayList<Meeting> A = new ArrayList<>();
class Meeting implements Comparable<Meeting> {
int start, end;
Meeting (int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Meeting o) {
if (this.end == o.end) // 종료시간이 같을 경우
return this.start - o.start; // 시작시간으로 오름차순 정렬
else // 기본적으로 종료시간 순으로 오름차순 정렬
return this.end - o.end;
}
}
public void InputData() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
//A = new Meeting[N];
for (int i=0; i<N; i++) {
int start = sc.nextInt();
int end = sc.nextInt();
//A[i] = new Meeting(start, end);
A.add(new Meeting(start, end));
}
}
public void Solve() {
//int count = 1;
//Arrays.sort(A);
int count = 0;
Collections.sort(A);
//int end_time = A[0].end;
// for (int i=1; i<N; i++) {
// if (end_time <= A[i].start) {
// end_time = A[i].end;
// count++;
// }
// }
int end_time = 0;
for (Meeting x : A) {
if (end_time <= x.start) {
end_time = x.end;
count++;
}
}
System.out.println(count);
}
public static void main(String[] args)
{
Main m = new Main();
m.InputData();///입력
//코드를 작성하세요
m.Solve();
}
}
[두번째]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Collections;
import java.lang.Comparable;
/*
1. 회의 정보(시작시간, 종료시간)를 저장하는 class를 정의한다. class meeting{int s, int e}
2. class를 오름차순으로 정렬하기 위해서 Comparable을 사용한다.
3. 회의 종료시간을 기준으로 meeting class를 오름차순으로 정렬한다.
4. 종료시간이 같은 회의는 시작시간이 빠른 회의가 앞에 가도록 한다.
5. 맨 앞의 회의부터 꺼내서 종료시간과 다음 회의의 시작시간을 비교해서 겹치지 않으면 스케쥴에 집어넣고 count++한다.
*/
public class Main {
static int N;
static ArrayList<Meeting> A;
class Meeting implements Comparable<Meeting> {
int s, e;
Meeting (int s, int e) {
this.s = s;
this.e = e;
}
@Override
public int compareTo(Meeting o) {
if (this.e == o.e) { // 종료시간이 같은 회의라면
return this.s - o.s; // 시작시간 작은 회의가 앞쪽에 위치
} else {
return this.e - o.e; // 종료시간이 작은 회의가 앞쪽에 위치
}
}
}
void Solve() {
int count = 0;
int end_time = 0;
Collections.sort(A); // ArrayList<Meeting>을 종료시간 기준으로 오름차순 정렬
for (Meeting now : A) {
if (end_time <= now.s) { // 앞 회의의 종료시간과 뒷 회의의 시작시간이 안 겹치면
end_time = now.e; // 뒷 회의의 종료시간으로 변수를 갱신하고
count++; // 스케쥴에 그 회의를 더한다
}
}
System.out.println(count);
}
void inputData() throws Exception {
InputStreamReader reader = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(reader);
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new ArrayList<Meeting>();
for (int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
A.add(new Meeting(s, e));
}
}
public static void main(String[] args) throws Exception {
Main m = new Main();
m.inputData(); // 입력 받는 부분
m.Solve();// 여기서부터 작성
}
}
댓글