1931번: 회의실 배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
회의실이 1개이고, 이를 사용할 수 있는 회의의 최대 갯수를 출력하는 문제입니다.
저는 회의 종료시간 기준으로 정렬한 후 그리디로 해결하였습니다.
회의 종료시간을 유지하면서 다음 회의부터 N까지 순회를 합니다.
현재 회의 종료시간이 다음 회의의 시작시간보다 작거나 같을때마다 종료시간을 갱신하고, ans를 1 늘려줍니다.
N번까지 순회 이후 ans를 출력합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int list[][];
static int N, ans = 1;
static void func() {
int e = list[0][1];
for (int i = 1; i < N; i++) {
if (e <= list[i][0]) {
e = list[i][1];
ans++;
}
}
System.out.println(ans);
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new int[N][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
list[i][0] = Integer.parseInt(st.nextToken());
list[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(list, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if (a[1] == b[1]) {
if (a[0] < b[0])
return -1;
else
return 1;
} else {
if (a[1] < b[1])
return -1;
else
return 1;
}
}
});
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > Greedy' 카테고리의 다른 글
| boj 8980 택배 (0) | 2021.02.16 |
|---|---|
| boj 11000 강의실 배정 (0) | 2021.02.16 |
| boj 2839 설탕 배달 (0) | 2021.02.16 |
| boj 11399 ATM (0) | 2021.01.29 |
| boj 1339 단어 수학 (0) | 2021.01.22 |