백준 1931, 회의실 배정 - Greedy
https://www.acmicpc.net/problem/1931
1. 아이디어
그리디 알고리즘 => 종료 시간이 빠른 순서로 회의를 선택
1) 입력 회의 배열을 종료 시간이 빠른 순서(오름차순)로 정렬
- 종료 시간이 동일하면, 시작 시간이 빠른 순서로 정렬
2) 정렬한 회의 배열을 반복문으로 확인
- (이전에 선택한 회의의 종료 시간 <= 다음 회의의 시작 시간) 을 만족하는 회의 선택
2. 자료구조
int
: 입력 N, numOfMeeting, 최대 10^5 (e^5)Meeting[]
: 입력 회의 배열 (회의 시작, 종료 시간 배열)
3. 시간 복잡도
Meeting[]
정렬: O(n log n)- 정렬된
Meeting[]
을 for 문으로 확인: O(n)
=> 총 O(n log n + n)
=> n 최대값 10^5 대입: 10^5 x 5 + 10^5 = 6 x 10^5 << 2억 (2초)
코드
import java.io.*;
import java.util.StringTokenizer;
import java.util.Arrays;
class Meeting implements Comparable<Meeting> {
private int start; // 회의 시작, 종료 시간
private int end;
public Meeting(int start, int end) {
this.start = start;
this.end = end;
}
public int getStart() { return start; }
public int getEnd() { return end; }
// 종료 시간이 빠른 순서로 정렬
// + 종료 시간이 동일하면, 시작 시간이 빠른 순서로 정렬
public int compareTo(Meeting m) {
int diffEnd = this.end - m.end;
if (diffEnd != 0)
return diffEnd;
else
return this.start - m.start;
}
}
public class Main {
static int n; // 전체 회의의 수
static Meeting[] meetings; // 회의 시작, 종료 배열
public static int solution() {
// 회의 배열 정렬
Arrays.sort(meetings);
// 회의 선택
int maxNum = 1; // 회의 최대 개수
Meeting current = meetings[0];
for (int i = 1; i < meetings.length; i++) {
if (current.getEnd() <= meetings[i].getStart()) {
current = meetings[i];
maxNum++;
}
}
return maxNum;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in)
);
StringTokenizer st;
n = Integer.parseInt(br.readLine());
meetings = new Meeting[n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
meetings[i] = new Meeting(start, end);
}
System.out.println(solution());
}
}
Author And Source
이 문제에 관하여(백준 1931, 회의실 배정 - Greedy), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@silver_star/백준-1931-회의실-배정-Greedy저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)